Masala #0965

Xotira 128 MB Vaqt 1500 ms
14

Do'st elflar

Shimoliy qutbda so'nggi yillarda dasturlashga e'tibor ancha kuchayib qoldi. Bu yili Qorbobo dasturchi elflarni bir joyga yig'ish maqsadida ular uchun ofis qurdirdi.

Dasturchi elflar oldindan alohida-alohida ishlagani uchun hech qaysi dasturchi elf bir-birini tanimaydi. Qorbobo esa jamoada hamma bir-birini tanishi muhim deb hisoblaydi. Shuning uchun u dasturchi elflarning ofisiga har kuni kelib ularni kuzata boshladi. U kuzatuvlarini yon daftariga quyidagicha yozib boradi.

  • \(!\space a \space b\) - a va b elfni birga yurganini ko'rsa shu ko'rinishda belgilab qo'yadi va ularni do'stlashgan deb hisoblaydi. Bu yerda a va b natural sonlardir, chunki Qorbobo elflarini raqamlab chiqqan (Kim ham minglab elf ismlarini eslab qolardi).
  • \(?\space a \space b\) - Qorbobo a va b elf do'stlashganmi deb o'ylab qolganda shu ko'rinishda belgilab qo'yadi. Bunda a elf b elf bilan va b elf c elf bilan do'st bo'lsa a elf c elf bilan ham do'st hisoblanadi (ya'ni do'stimning do'sti mening ham do'stim).

Siz Qorboboning yon daftaridagi har bir so'rovga javob bering. \(!\space a \space b\) ko'rinishidagi so'rovda a va b ni do'stlashtiring, \(?\space a \space b\) ko'rinishidagi so'rovda esa a va b elf do'st yoki do'st emasligini aniqlang.


Kiruvchi ma'lumotlar:

Brinchi qatorda N va Q sonlari \((1<N\leq 2*10^5; 1\leq Q \leq 2*10^5)\), mos ravishda dasturchi elflar soni va Qorboboning yon daftaridagi so'rovlar soni. Keyingi Q ta qatorda so'rovlar:
    \(!\space a \space b\) yoki \(?\space a \space b\) ko'rinishida \((a \not= b)\), kamida bitta \(?\space a \space b\) ko'rinishida so'rov borligi kafolatlanadi.


Chiquvchi ma'lumotlar:

\(!\space a \space b\) ko'rinishidagi so'rovda a va b ni do'stlashtiring, \(?\space a \space b\) ko'rinishidagi so'rovda esa a va b elf do'st bo'lsa 1 aks holda 0 chiqaring.


Misollar
# input.txt output.txt
1
5 5
! 1 2
! 3 4
! 2 4
? 1 3
? 3 5
1 0
2
5 3
? 1 2
! 1 2
? 1 2
0 1