eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Сумма игр

Сумма игр

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

Пусть дан ориентированный граф. Стандартная игра на графе заключается в следующем: изначально на одной из вершин графа (называемой начальной позицией) стоит фишка. Двое игроков по очереди двигают её по рёбрам. Проигрывает тот, кто не может сделать ход.

В теории игр часто рассматриваются более сложные игры. Например, прямая сумма двух игр на графах. Прямая сумма игр — это следующая игра: изначально на каждом графе в начальной позиции стоит по фишке. За ход игрок выбирает любую фишку и двигает по ребру соответствующего графа. Проигрывает тот, кто не может сделать ход.

Ваша задача — опеределить, кто выиграет при правильной игре.

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

На первой строке будут даны числа N_1 и M_1 — количество вершин и рёбер в первом графе (1N_1, M_110000). На следующих M_1 строках содержится по два числа x и y (1x, yN_1).

В следующих M_2+1 строках задан второй граф в том же формате.

Заканчивается входной файл списком пар начальных вершин, для которых нужно решить задачу. На первой строке задано число T (1T100000) — количество пар начальных вершин. В следующих T строках указаны пары вершин v_1 и v_2 (1v_1N_1, 1v_2N_2).

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

На каждую из T пар начальных вершин выведите строку "first", если при правильной игре выиграет первый, "second", если второй, или "draw", если будет ничья.

Пример

Входные данные #1
3 2
1 2
2 3
2 1
1 2
2
1 1
3 2
Выходные данные #1
first
second
Источник III Международная Летняя школа программирования 2012 г. Севастополь