Problem A
Disjunkte mængder

Vedligehold en familie af disjunkte mængder, oprindeligt etpunktsmængderne $ \{ 0\} ,\{ 1\} , \ldots ,\{ 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\neq 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\neq 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\neq 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\leq s< n$, $0\leq t< n$ og $m\geq 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