|
Remote Training on Programming
|
||||||||||
|
|
|||||||||||
| Hello, Guest! Please login or register. |
1618. Multiplication of Graphs
|
| View Problem Statistics | Submit | Problem added 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
|
| View Problem Statistics | Submit | Problem discussion | Author/source: |
| Problems from Contests and Camps / | Trainings in Perm 2009 / | 10.07.09 Small Contest / |
| 1617. B - Japanese Computer | 1618. |
| time generating 0.109 sec. |
| © Copyright VSU, AVT, Nosov D.A., Andrianov I.A. |