Колобок: факти та фікції
Обмеження: 2 сек., 256 МіБ
Усі знають казку про Колобка — про те, як шматок хліба вирвався з хати, почав бігати по дорогах та зустрічати різних звірів.
Вченим достовірно відомо, як виглядав ліс, яким рухався Колобок. Він складався з n полян, деякі з яких були з’єднані двосторонніми дорогами. Точно відомо, що доріг було n−1, а також, що від кожної поляни можна було добратись до будь-якої іншої (можливо, проходячи через інші поляни). Крім цього, відомо, що Колобок почав свій шлях на деякій поляні, а потім пройшовся певною кількістю доріг, при цьому не відвідуючи жодну поляну більше одного разу.
Однак нікому до кінця не відомо, яким саме маршрутом ішов Колобок. У народі з’явилося багато версій, деякі з них цілком імовірні, а деякі — повні нісенітниці. Кожна версія — це певний набір полян, які, як стверджують певні люди, Колобок точно відвідав на своєму шляху.
Ваше завдання — для кожної версії визначити, чи міг цей набір бути набором полян (можливо, не повним), які відвідав Колобок.
Вхідні дані
У першому рядку задано два цілих числа n та m — кількість полян у лісі та кількість версій відповідно. Поляни пронумеровані цілими числами від 1 до n включно.
У наступних n−1 рядках задано дороги, по одній дорозі в рядку. Кожна дорога задана парою чисел ai та bi — номерами полян, які сполучає відповідна дорога.
У наступних m рядках описано версії, по одній версії в рядку. Опис версії починається з цілого числа ki — кількості полян, які містить відповідна версія. Далі містяться ki цілих чисел pij, які задають номери полян у відповідній версії (в довільному порядку).
Вихідні дані
Для кожної версії виведіть Tak, якщо це версія
правдоподібна, і Ni в протилежному разі.
Обмеження
40% тестів: 1≤n,m,s≤250,
60% тестів: 1≤n,m,s≤105,
де s — сумарна кількість полян у всіх версіях,
гарантується, що в кожній версії всі номери полян різні.
Приклади
| Вхідні дані (stdin) | Вихідні дані (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 |