CSES - Dynaaminen yhtenäisyys
  • Time limit: 2.00 s
  • Memory limit: 128 MB
Verkossa on $n$ solmua, jotka on numeroitu $1 \ldots n$. Aluksi verkossa ei ole yhtään kaarta. Vastaa kyselyihin:
  1. Lisää kaari solmujen $a$ ja $b$ välille
  2. Poista kaari solmujen $a$ ja $b$ väliltä
  3. Laske montako yhdistynyttä komponenttia verkossa on
Syöte
Syötteen ensimmäisellä rivillä on $n$ ja $q$, solmujen määrä ja kyselyiden määrä.

Seuraavalla $q$ rivillä on kyselyt. Rivin alussa on kyselyn tyyppi. Jos kyselyn tyyppi on 1 tai 2, sen jälkeen syötteessä on $a$ ja $b$.

Verkossa ei ole koskaan kahta kaarta saman solmuparin välillä. Kyselyn 2 tapahtuessa on aina olemassa kaari solmujen $a$ ja $b$ välillä.

Tuloste
Tulosta vastaus jokaiselle 3 tyypin kyselylle

Rajat
  • $2 \le n \le 3 \cdot 10^5$
  • $1 \le q \le 3 \cdot 10^5$
  • $1 \le a, b \le n$, $a \neq b$
Esimerkki

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


Tuloste:
5
4
3
2
3
2
2
2
3