Problem A
Disjunkte mængder (enkel)

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

? (»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$.

= (»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.)

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

Testgrupper

Der er to 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 »? $s$ $t$« eller »= $s$ $t$«, for henholdsvis forespørgsel og forening. 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 1
= 0 1
? 0 1
= 1 2
? 1 2
? 0 3
= 2 3
? 2 3
? 0 3

0
1
1
0
1
1

2 2
= 0 0
? 0 1

0