Колобок: факти та фікції

Обмеження: 2 сек., 256 МіБ

Усі знають казку про Колобка — про те, як шматок хліба вирвався з хати, почав бігати по дорогах та зустрічати різних звірів.

Вченим достовірно відомо, як виглядав ліс, яким рухався Колобок. Він складався з \(n\) полян, деякі з яких були з’єднані двосторонніми дорогами. Точно відомо, що доріг було \(n-1\), а також, що від кожної поляни можна було добратись до будь-якої іншої (можливо, проходячи через інші поляни). Крім цього, відомо, що Колобок почав свій шлях на деякій поляні, а потім пройшовся певною кількістю доріг, при цьому не відвідуючи жодну поляну більше одного разу.

Однак нікому до кінця не відомо, яким саме маршрутом ішов Колобок. У народі з’явилося багато версій, деякі з них цілком імовірні, а деякі — повні нісенітниці. Кожна версія — це певний набір полян, які, як стверджують певні люди, Колобок точно відвідав на своєму шляху.

Ваше завдання — для кожної версії визначити, чи міг цей набір бути набором полян (можливо, не повним), які відвідав Колобок.

Вхідні дані

У першому рядку задано два цілих числа \(n\) та \(m\) — кількість полян у лісі та кількість версій відповідно. Поляни пронумеровані цілими числами від 1 до \(n\) включно.

У наступних \(n-1\) рядках задано дороги, по одній дорозі в рядку. Кожна дорога задана парою чисел \(a_i\) та \(b_i\) — номерами полян, які сполучає відповідна дорога.

У наступних \(m\) рядках описано версії, по одній версії в рядку. Опис версії починається з цілого числа \(k_i\) — кількості полян, які містить відповідна версія. Далі містяться \(k_i\) цілих чисел \(p_{ij}\), які задають номери полян у відповідній версії (в довільному порядку).

Вихідні дані

Для кожної версії виведіть Tak, якщо це версія правдоподібна, і Ni в протилежному разі.

Обмеження

40% тестів: \(1 \le n, m, s \le 250\),

60% тестів: \(1 \le n, m, s \le 10^5\),

де \(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