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

Сума ігр

Сума ігр

Нехай задано орієнтовний граф. Стандартна гра на графі полягає у наступному: спочатку на одній з вершин графа (так званій початковій позиції) стоїть фішка. Двоє гравців по черзі рухають її по рёбрам. Програє той, хто не може зробити хід. У теорії ігр часто розглядаються більш складні ігри. Наприклад, пряма сума двох ігр на графах. Пряма сума ігр --- це наступна гра: спочатку на кожному графі у початковій позиції стоїть по фішці. За хід гравець вибирає довільну фішку і рухає по ребру відповідного графа. Програє той, хто не може зробити хід. Ваша задача --- визначити, хто виграє при правильній грі. \InputFile У першому рядку будуть задані числа \textbf{N_1} та \textbf{M_1} --- кількість вершин та ребер у першому графі (\textbf{1} ≤ \textbf{N_1}, \textbf{M_1} ≤ \textbf{10000}). У наступних \textbf{M_1} рядках міститься по два числа \textbf{x} та \textbf{y} (\textbf{1} ≤ \textbf{x}, \textbf{y} ≤ \textbf{N_1}). У наступних \textbf{M_2+1} рядках задано другий граф у тому ж форматі. Закінчується вхідной файл списком пар початкових вершин, для яких потрібно розв'язати задачу. У першому рядку задано число \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{100000}) --- кількість пар початкових вершин. У наступних \textbf{T} рядках вказані пари вершин \textbf{v_\{1 \}}та \textbf{v_2} (\textbf{1} ≤ \textbf{v_1} ≤ \textbf{N_1}, \textbf{1} ≤ \textbf{v_2} ≤ \textbf{N_2}). \OutputFile Для кожної з \textbf{T} пар початкових вершин виведіть рядок "\textbf{first}", якщо при правильній грі виграє перший, "\textbf{second}", якщо другий, або "\textbf{draw}", якщо буде нічия.
Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
3 2
1 2
2 3
2 1
1 2
2
1 1
3 2
Вихідні дані #1
first
second
Джерело III Міжнародна Літня школа програмування 2012 м. Севастополь