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

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

Ограничение по времени Ограничение по памяти
2 секунды 256 мегабайт

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

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

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

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

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

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

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

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

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

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

Примеры

Вход

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

Выход

1 0 1