Добуток графів#1750
Нехай дано ациклічний орієнтований граф. Опис стандартної гри на графі: спочатку фішка розташовується на одній з вершин графа (її називають початковою позицією). Двоє гравців по черзі пересувають фішку вздовж ребер. Програє той гравець, котрий не може здійснити хід.
У теорії ігор часто розглядають складніші ігри. Наприклад, прямий добуток двох ігор на графах. Гра у прямий добуток визначається так: спочатку в кожному графі фішка розташовується у своїй початковій позиції. На кожному ході гравець переміщує обидві фішки вздовж ребер (кожну фішку всередині відповідного графа). Програє той гравець, котрий не може здійснити хід — тобто той, хто не може зробити хід хоча б в одній з ігор.
Ваше завдання — визначити, хто переможе за умови оптимальної гри.
У першому рядку задано числа N_1 і M_1 — кількість вершин і ребер у першому графі (1 \leq N_1, M_1 \leq 100000). Кожен з наступних M_1 рядків містить два числа та (1 \leq x, y \leq N_1).
Далі йдуть M_2 + 1 рядків, які так само описують другий граф.
Після цього вводиться список пар початкових вершин. Перший з цих рядків містить (1 \leq T \leq 100000) — кількість пар початкових позицій. Кожен з наступних рядків містить пару v_1 і v_2 (1 \leq v_1 \leq N_1, 1 \leq v_2 \leq N_2).
Для кожної з пар початкових вершин виведіть у окремому рядку "first", якщо при оптимальній грі виграє перший гравець, і "second" інакше.
Приклад 1