G. Сколько продлится партия

Та же игра, что в задаче F, но теперь мало знать исход. Выигрывающий хочет закончить как можно быстрее, проигрывающий - продержаться как можно дольше. Сколько ходов продлится партия?

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

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

Для каждой вершины выведите строку.

Если выигрывает первый - «FIRST k», если второй - «SECOND k», где $k$ - число ходов в партии при оптимальной игре обоих. Если ничья - «DRAW».