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