Колобок: факти та фікції
Limits: 2 sec., 256 MiB
Усі знають казку про Колобка — про те, як шматок хліба вирвався з хати, почав бігати по дорогах та зустрічати різних звірів.
Вченим достовірно відомо, як виглядав ліс, яким рухався Колобок. Він складався з \(n\) полян, деякі з яких були з’єднані двосторонніми дорогами. Точно відомо, що доріг було \(n-1\), а також, що від кожної поляни можна було добратись до будь-якої іншої (можливо, проходячи через інші поляни). Крім цього, відомо, що Колобок почав свій шлях на деякій поляні, а потім пройшовся певною кількістю доріг, при цьому не відвідуючи жодну поляну більше одного разу.
Однак нікому до кінця не відомо, яким саме маршрутом ішов Колобок. У народі з’явилося багато версій, деякі з них цілком імовірні, а деякі — повні нісенітниці. Кожна версія — це певний набір полян, які, як стверджують певні люди, Колобок точно відвідав на своєму шляху.
Ваше завдання — для кожної версії визначити, чи міг цей набір бути набором полян (можливо, не повним), які відвідав Колобок.
Input
У першому рядку задано два цілих числа \(n\) та \(m\) — кількість полян у лісі та кількість версій відповідно. Поляни пронумеровані цілими числами від 1 до \(n\) включно.
У наступних \(n-1\) рядках задано дороги, по одній дорозі в рядку. Кожна дорога задана парою чисел \(a_i\) та \(b_i\) — номерами полян, які сполучає відповідна дорога.
У наступних \(m\) рядках описано версії, по одній версії в рядку. Опис версії починається з цілого числа \(k_i\) — кількості полян, які містить відповідна версія. Далі містяться \(k_i\) цілих чисел \(p_{ij}\), які задають номери полян у відповідній версії (в довільному порядку).
Output
Для кожної версії виведіть Tak, якщо це версія
правдоподібна, і Ni в протилежному разі.
Constraints
40% тестів: \(1 \le n, m, s \le 250\),
60% тестів: \(1 \le n, m, s \le 10^5\),
де \(s\) — сумарна кількість полян у всіх версіях,
гарантується, що в кожній версії всі номери полян різні.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 7 4 4 7 1 4 3 1 3 6 5 3 2 1 1 4 3 1 6 5 3 4 7 2 4 1 2 3 4 | Tak Ni Tak Ni |
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|