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

Обмеження: 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$ — сумарна кількість полян у всіх версіях,

гарантується, що в кожній версії всі номери полян різні.

Приклади