EduBrick

F. Ретроанализ наоборот

1000 мс · 256 МБ · всё или ничего

Тот же граф и та же фишка, что в классной задаче F, но правило конца перевёрнуто: выигрывает тот, кто не может сделать ход.

Меняется ровно одна строка, и полезно понять, почему именно одна.

Формат ввода

В первой строке - числа nn и mm (1≤n,m≤3⋅1051 \le n, m \le 3 \cdot 10^5).

В следующих mm строках - рёбра. Возможны петли и кратные рёбра.

Формат вывода

Для каждой вершины выведите FIRST, SECOND или DRAW - кто выигрывает при старте из неё, если победителем считается тот, кто не может сходить.

Примеры

ввод
2 1
1 2
вывод
SECOND
FIRST
ввод
5 5
1 2
2 3
3 1
1 4
4 5
вывод
FIRST
FIRST
SECOND
SECOND
FIRST
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.