Laiko ribojimas: 1s

Atminties ribojimas: 1024MB

Duomenų failas: friend_the_third.in

Rezultatų failas: friend_the_third.out

Jei norite pateikti savo sprendimą - prisijunkite.

1. Draugai

Džozefas Antrasis neseniai susidomėjo savo draugų ratu. Tiksliau - jis panoro sužinoti, ar tam tikru momentu du jo pažystami buvo draugai. Džozefui Antrajam šio uždavinio išspręsti nepavyko, todėl jis prašo jūsų jam padėti.

Džozefas jums pateikia m užklausų, aprašytų simboliu c_i ir dviem sveikaisiais skaičiais a_i, b_i.

  1. Jei c_i= - tai reiškia, jog a_i ir b_i tapo draugais.
  2. Jei c_i= - tai reiškia, jog Džozefas nori sužinoti, ar tuo momentu a_i ir b_i jau buvo draugais.

Džozefas tiki, jog jei a yra b yra draugai bei b ir c yra draugai, tai ir a ir c taip pat yra draugai.

Padėkite Džozefui rasti atsakymus į jo klausimus.

Pradiniai duomenys

Pirmoje eilutėje pateikti du sveikieji skaičiai n ir m (1\\leqn,m\\leq10^6) - Džozefo žinomų žmonių skaičius bei užklausų kiekis. Sekančiose m eilučių pateiktas simbolis c_i, bei du sveikieji skaičiai a_i,b_i (1\\leqa_i,b_i\\leqn) - užklausos duomenys.

Rezultatai

Kiekvienai antro tipo užklausai naujoje eilutėje išveskite "TAIP", jei a_i bei b_i tuo momentu buvo draugai, kitu atveju išveskite "NE".

Pavyzdžiai

Pradiniai duomenys Rezultatai 
10 7
+ 1 2
? 3 1
+ 2 3
+ 3 4
+ 4 5
? 4 2
+ 6 7
 
NE
TAIP