Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Lentokentät

Lentokentät


View task | Model solution | Statistics


Lentokentät

Time limit:1.00 s
Memory limit:128 MB

Bittimaassa on $n$ lentokenttää. Aluksi kenttien välillä ei ole mitään yhteyksiä, mutta uusia yhteyksiä avataan jatkuvasti. Tehtäväsi on selvittää hetki, jolloin miltä tahansa kentältä pääsee mille tahansa kentälle.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$: lentokenttien määrä ja yhteyksien määrä. Lentokentät on numeroitu $1,2,\ldots,n$.

Sitten syötteessä on $m$ riviä, joista jokainen kuvaa uuden yhteyden. Jokaisella rivillä on kokonaisluvut $a$ ja $b$: minkä kenttien välillä on yhteys on. Yhteydet avataan syötteen järjestyksessä.

Tuloste

Tulosta, montako yhteyttä täytyy avata, ennen kuin kaikki kentät ovat yhteydessä toisiinsa. Jos tämä ei toteudu koskaan, tulosta "QAQ".

Rajat
Esimerkki

Syöte:
5 7
1 2
4 5
3 4
3 5
1 4
2 3
1 5


Tuloste:
5