Улак-тартыш


Отправить решение Решать в редакторе

Сложность: 70%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

На джайлоо у подножия Алайского хребта ребята придумали настольную версию улак-тартыша. Поле — это n пастбищ, соединённых m горными тропами. Каждая тропа ведёт от одного пастбища к другому и проходится только в одном направлении — вниз по склону, поэтому, двигаясь по тропам, нельзя вернуться на уже пройденное пастбище (циклов нет).

На поле расставлены фишки-всадники, на одном пастбище может стоять сколько угодно всадников. Эрлан и Мирлан ходят по очереди, начинает Эрлан. За один ход игрок выбирает одного любого всадника и передвигает его по одной тропе на соседнее пастбище. Кто не может сделать ход (все всадники стоят на пастбищах, откуда троп нет), тот проиграл.

Ребята сыграли q партий на одном и том же поле, каждый раз с новой расстановкой всадников. Для каждой партии определите, сколько у Эрлана выигрышных первых ходов — таких ходов, после которых он гарантированно побеждает при любой игре Мирлана. Если таких ходов нет, при правильной игре Мирлана Эрлан проиграет.

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

Входные данные

В первой строке — два целых числа n и m (1 ≤ n ≤ 200 000, 0 ≤ m ≤ 500 000).

В каждой из следующих m строк — два числа a и b (1 ≤ a, b ≤ n, a ≠ b): тропа ведёт с пастбища a на пастбище b. Гарантируется, что циклов нет и никакая тропа не повторяется.

Далее — число q (1 ≤ q ≤ 200 000). В каждой из следующих q строк описана партия: сначала число всадников k (k ≥ 1), затем k номеров пастбищ, на которых они стоят. Сумма всех k не превосходит 1 000 000.

Выходные данные

Для каждой партии выведите в отдельной строке количество выигрышных первых ходов Эрлана.

Пример 1

Вход:

5 5
1 2
2 3
1 3
3 4
2 5
4
1 1
2 2 3
3 1 1 4
2 2 5

Выход:

0
1
0
1

Пояснение

В первой партии единственный всадник стоит на пастбище 1. Любой ход Эрлана (на пастбище 2 или 3) оставляет Мирлану выигрышную позицию, поэтому ответ 0.

Во второй партии выигрывает только ход 2 → 3: после него оба всадника стоят на пастбище 3, и на любой ход Мирлана Эрлан отвечает тем же ходом вторым всадником.

Система оценивания

Подзадача Баллы Дополнительные ограничения
1 15 n ≤ 8, m ≤ 14, k ≤ 4
2 20 в каждой партии ровно один всадник
3 20 n, m ≤ 2000, сумма k ≤ 10 000
4 45 без дополнительных ограничений

Баллы за подзадачу начисляются, только если пройдены все её тесты.


Комментарии

Еще нет ни одного комментария.