Masala #0965
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.
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.
\(!\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.
# | 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 |