|
Дистанционный практикум по программированию
|
||||||||||
|
|
|||||||||||
| Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь. |
1618. Произведение графов
|
| Статистика | Послать на проверку | Задачу добавил debug |
|
Пусть дан ориентированный ациклический граф. Стандартная игра на графе заключается в следующем: изначально на одной из вершин графа (называемой начальной позицией) стоит фишка. Двое игроков по очереди двигают её по рёбрам. Проигрывает тот, кто не может сделать ход. В теории игр часто рассматриваются более сложные игры. Например, прямое произведение двух игр на графах. Прямое произведение игр — это следующая игра: изначально на каждом графе в начальной позиции стоит по фишке. За ход игрок двигает обе фишки по рёбрам (каждую фишку двигает в собственном графе). Проигрывает тот, кто не может сделать ход. То есть тот, кто не может сделать ход хотя бы в одной игре. Ваша задача — опеределить, кто выиграет при правильной игре. Входные данные На первой строке будут даны числа N1 и M1 — количество вершин и рёбер в первом графе (1 ≤ N1, M1 ≤ 100 000). На следующих M1 строках содержится по два числа x и y (1 ≤ x, y ≤ N1). В следующих M2 + 1 строках задан второй граф в том же формате. Заканчивается входной файл списком пар начальных вершин, для которых нужно решить задачу. На первой строке задано число T (1 ≤ T ≤ 100 000) — количество пар начальных вершин. В следующих T строках указаны пары вершин v1 и v2 (1 ≤ v1 ≤ N1, 1 ≤ v2 ≤ N2). Учтите, что в графах могут быть кратные рёбра. Выходные данные На каждую из T пар начальных вершин выведите строку "first", если при правильной игре выиграет первый, и "second", если второй. Пример Входные данные 3 2 Выходные данные first
|
| Статистика | Послать на проверку | Обсуждение задачи | Автор/источник: |
| Задачи с соревнований и сборов / | Сборы в Перми 2009 / | 10.07.09 Малый контест / |
| 1617. B - Японский компьютер | 1618. |
| время генерации 0.11 сек. | |
| © Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А. |