G. Куда пойти

Тот же граф, что в классной задаче F. Для каждой выигрышной вершины назовите, в какую вершину надо сходить.

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

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

Для каждой вершины выведите наименьший номер вершины, ходом в которую первый игрок выигрывает, либо 0, если такого хода нет.