Problem B
Disjunkte mængder

Vedligehold en familie af disjunkte mængder, oprindeligt etpunktsmængderne $\{0\},\{1\},\dots ,\{n-1\}$, under følgende operationer:

0 (»forespørgsel«)

Forespørgslen tager to elementer $s$ og $t$ og afgør, om $s$ og $t$ tilhører samme mængde. Mere nøjagtigt gælder, at når $s\in S$ og $t\in T$, så er svaret »1« hvis $S=T$ og »0« hvis $S\ne T$.

1 (»forening«)

Foreningsoperationen tager to elementer $s$ og $t$ og danner foreningsmængden af de to mænger, der indeholder $s$ og $t$. Mere nøjagtigt gælder, at når $s\in S$ og $t\in T$ med $S\ne T$, så fjernes $S$ og $T$ fra familjen, og mængden $S\cup T$ tilføjes. (Når $S=T$, sker der ingenting.)

2 (»flytning«)

(Flytning forekommer kun i testgrupperne 2 og 4.) Flytningsoperationen tager to elementer $s$ og $t$ og flytter elementet $s$ til mængden indeholdende elementet $t$. Mere nøjagtigt gælder, at når $s\in S$ og $t\in T$ med $S\ne T$, så ændres $S$ til $S-\{s\}$ og $T$ til $T\cup \{s\}$. (Når $S=T$, sker der ingenting.)

Læg mærke til, at disse operationer opretholder invarianten om, at familjens mængder er disjunkte.

Testgrupper

Der er fire testgrupper.

Hver løsning til testgruppe 3 løser også testgruppe 1. Hver løsning til testgruppe 4 løser alle andre testgrupper.

Indlæsning

Indlæsningen begynder med to positive heltal $n$, $m$ på første linje. Tallet $n$ er antallet af oprindelige etpunksmængder. De følgende $m$ linjer har formen »0 $s$ $t$« eller »1 $s$ $t$« eller »2 $s$ $t$«, for henholdvis forespørgsel, forening og flytning. Flytning forekommer ikke i testgrupperne 1 og 3. Du kan antage $0\le s<n$, $0\le t<n$ og $m\ge 1$.

Udskrift

For hver forespørgsel, skriv en linje med »1« eller »0« som beskrevet foroven.

4 9
0 0 1
1 0 1
0 0 1
1 1 2
0 1 2
0 0 3
1 2 3
0 2 3
0 0 3

0
1
1
0
1
1

4 9
0 0 1
1 0 1
0 0 1
1 1 2
0 1 2
0 0 3
2 2 3
0 0 1
0 1 2

0
1
1
0
1
0

2 2
1 0 0
0 0 1

0