- Time limit: 1.00 s
- Memory limit: 128 MB
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ä.
Mikään yhteys ei ole kentästä itseensä, ja jokaisen kahden kentän välille avataan enintään yksi yhteys.
Tuloste
Tulosta, montako yhteyttä täytyy avata, ennen kuin kaikki kentät ovat yhteydessä toisiinsa. Jos tämä ei toteudu koskaan, tulosta "QAQ".
Rajat
- $2 \le n \le 10^5$
- $0 \le m \le 2 \cdot 10^5$
- $1 \le a,b \le n$
Syöte:
5 7
1 2
4 5
3 4
3 5
1 4
2 3
1 5
Tuloste:
5