Республиканская олимпиада по информатике 2019 года за 10 класс | Казахстанские олимпиады

Задача C. Маглы наступают

Интернет в мире представляется в виде $n$ вершин и $n - 1$ ребер, каждое ребро соединяет две вершины, и возможно добраться из каждой вершину в каждую, передвигаясь по ребрам.

В каждой вершине живет Волшебник. Волшебники — очень дружелюбные существа, но они могут существовать только парами. 2 Волшебника являются парой, если они находятся в соседних вершинах и решили быть парой. У Волшебника не может быть большой одной пары.

Маглы решили заблокировать некоторые вершины дерева, а заодно и забрать Волшебников, живущих в них. Каждая блокировка представляет собой $k$ вершин дерева, которые будут заблокированы. Из каждой заблокированной вершины Маглы забирают Волшебника. После блокировки наступает паника и Волшебники ищут себе пару. Если хотя бы один Волшебник (среди тех, кого не забрали) не найдет себе пару, наступает Хаос.

Формат входного файла

В первой строке входных данных дается два числа $n$, $q$ ($1 <= n, q <= 5*10^5$) — количество вершин и количество предположений блокировок соответственно.

В следующих $n-1$ строках даются два числа $u$, $v$ ($1 <= u, v <= n$) — вершины, между которыми есть ребро.

В следующих $q$ строках подаются описания блокировок в следующем виде:

$k, a_1, a_2, \dots, a_k$ $(0 <= k <= n, 1 <= a_i <= n)$ — количество и номера заблокированных вершин.

Формат выходного файла

Выведите $q$ чисел, разделенных пробелами. Для каждой блокировки в порядке входных данных выведите $1$, если все Волшебники смогут разбиться на пары (Хаос не наступит), и $0$, если нет (Хаос наступит).

Примеры

Вход

3 3
1 2
2 3
1 1
1 2
1 3

Выход

1 0 1