RC5-E. Choyxonalar

Viloyatda N ta qishloq bor, ular N − 1 ta yo‘l bilan shunday bog‘langanki, istalgan qishloqdan istalganiga yetib borish mumkin (ya’ni yo‘llar daraxt hosil qiladi). Har qishloqda bitta choyxona bor va unda faqat bir xil choy damlanadi: K — ko‘k choy yoki Q — qora choy.

M ta sayohatchi bor. j-sayohatchi aⱼ qishloqdan bⱼ qishloqqa yagona yo‘l bo‘ylab (hech bir qishloqqa ikki marta kirmasdan) boradi va yo‘lda o‘zi yoqtirgan wⱼ choyni ichmoqchi. Boshlang‘ich va oxirgi qishloq ham yo‘lga kiradi.

Har bir sayohatchi uchun aniqlang: uning yo‘lida yoqtirgan choyi damlanadigan choyxona bormi?

Kirish ma’lumotlari

Birinchi qatorda ikkita butun son N va M.

Ikkinchi qatorda N ta harfdan iborat satr: i-harf (K yoki Q) — i-qishloqdagi choy.

Keyingi N − 1 ta qatorning har birida ikkita son u va v — u va v qishloqlarni bog‘lovchi yo‘l.

Keyingi M ta qatorning j-sida ikkita son aⱼ, bⱼ va harf wⱼ (K yoki Q).

Chiqish ma’lumotlari

M ta belgidan iborat bitta satr: j-belgi 1, agar j-sayohatchi yoqtirgan choyini ichishi mumkin bo‘lsa, aks holda 0.

Cheklovlar

• 1 ≤ N, M ≤ 2·10⁵
• 1 ≤ u, v, aⱼ, bⱼ ≤ N; aⱼ = bⱼ bo‘lishi mumkin

1-misol: 1-sayohatchining yo‘li 1 → 2 → 4, hamma joyda ko‘k choy — 0. 2-sining yo‘li 1 → 2 → 3 → 5, 3-qishloqda qora choy bor — 1. 3-si 4-qishloqdan chiqmaydi, u yerda ko‘k choy — 1. 4-sining yo‘li 5 → 3, ikkalasida qora choy — 0.