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ä.

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$

Esimerkki

Syöte:

5 7
1 2
4 5
3 4
3 5
1 4
2 3
1 5

Tuloste:

5