Улак-тартыш
На джайлоо у подножия Алайского хребта ребята придумали настольную версию улак-тартыша. Поле — это 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 | без дополнительных ограничений |
Баллы за подзадачу начисляются, только если пройдены все её тесты.
Комментарии