ŠIOM — Gaujų karai

Laiko ribojimas: 1s

Atminties ribojimas: 16MB

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Gaujų karai

Mokiniai mokykloje pradėjo skirstytis į gaujas (neklauskite kodėl). Kiekvienai gaujai priklauso bent vienas mokinys. Be to, kiekvienoje gaujoje lygiai vienas mokinys yra paskiriamas vadu. Mokykloje iš viso yra $n$ mokinių ir iš pradžių jie visi yra skirtingose gaujose (t.y. gaujose iš vieno žmogaus).

Būti vienam gaujoje nėra labai įdomu, todėl mokiniai pradėjo jungtis. Gaujų susijungimas vyksta taip: dviem gaujoms (pavadinkim jas $A$ ir $B$ ) susitarus susijungti, susiformuoja nauja gauja $C$ , kurią sudaro visi mokiniai tiek iš gaujos $A$ , tiek iš gaujos $B$ , o senųjų gaujų nebelieka. Naujos gaujos vadu paskiriamas mokinys, kuris buvo didesniosios iš gaujų $A$ ir $B$ vadas (gaujos dydis matuojamas mokinių, priklausančių gaujai, skaičiumi). Jei gaujų dydžiai lygūs, vadu paskiriamas antrosios gaujos (t.y. gaujos $B$ ) vadas.

Kaip galite nuspėti, visi šie susijungimai labai greitai gali tapti painiu reikalu. Taip galvoja ir mokytojas Margiris. Jam kartas nuo karto gali prireikti sužinoti tam tikrą informaciją apie gaujas bei konkrečius mokinius:

Ar mokiniai $x$ ir $y$ priklauso vienai gaujai?
Koks yra gaujos, kuriai priklauso mokinys $x$ , dydis?
Kas yra gaujos, kuriai priklauso mokinys $x$ , vadas?

Negana to, Margiris gali užduoti tokius klausimus dar gaujoms besiformuojant (t.y. gaujų formavimasis ir mokytojo klausimai gali vykti beveik vienu metu). Kam mokytojui Margiriui tos informacijos reikia? Čia jau paslaptis :). Tačiau nepaisydami to, padėkite jam atsakyti į užklausas!

Pradiniai duomenys

Pirmoje eilutėje pateikti du sveikieji skaičiai $n$ ir $q$ - mokinių skaičius ir užklausų kiekis ( $1\\leqn,q\\leq10^5$ ).

Toliau seka $q$ eilučių, reiškiančių pačias užklausas. Užklausų formatas yra toks:

$\\texttt{+xy}$ - gaujos, kurioms priklauso mokiniai $x$ ir $y$ , susijungia.
$\\texttt{\#x}$ - koks gaujos, kuriai priklauso mokinys $x$ , dydis?
$\\texttt{!x}$ - kas yra gaujos, kuriai priklauso mokinys $x$ , vadas?
$\\texttt{?xy}$ - ar mokiniai $x$ ir $y$ priklauso vienai gaujai?

Mokiniai numeruojami nuo $1$ iki $n$ .

Pastaba. Kartais mokiniai gali suklysti ir bandyti sujungti savo gaujas net tada, kai jie ir taip jau yra vienoje gaujoje. Tokiu atveju jums nieko daryti nereikia :)

Rezultatai

Kiekvienai mokytojo užklausai reikia atspausdinti po vieną eilutę. $\\texttt{?}$ tipo užklausai reikia atspausdinti žodį taip, jei mokiniai yra vienoje gaujoje, ir ne kitu atveju. $\\texttt{+}$ tipo užklausoms nieko spausdinti nereikia.

Pavyzdžiai

Pradiniai duomenys	Rezultatai
3 29 # 1 # 2 # 3 ! 1 ! 2 ! 3 ? 1 2 ? 1 3 ? 2 3 + 1 2 # 1 # 2 # 3 ! 1 ! 2 ! 3 ? 1 2 ? 1 3 ? 2 3 + 1 3 # 1 # 2 # 3 ! 1 ! 2 ! 3 ? 1 2 ? 1 3 ? 2 3	1 1 1 1 2 3 ne ne ne 2 2 1 2 2 3 taip ne ne 3 3 3 2 2 2 taip taip taip

Pradiniai duomenys

Rezultatai

3 29
# 1
# 2
# 3
! 1
! 2
! 3
? 1 2
? 1 3
? 2 3
+ 1 2
# 1
# 2
# 3
! 1
! 2
! 3
? 1 2
? 1 3
? 2 3
+ 1 3
# 1
# 2
# 3
! 1
! 2
! 3
? 1 2
? 1 3
? 2 3

1
1
1
1
2
3
ne
ne
ne
2
2
1
2
2
3
taip
ne
ne
3
3
3
2
2
2
taip
taip
taip

Šeštadieninė informatikos olimpiadininkų mokykla

Gaujų karai

Pradiniai duomenys

Rezultatai

Pavyzdžiai