K. Одностороннее движение

В стране $n$ городов и $m$ двусторонних дорог; из любого города можно доехать до любого. Все дороги делают односторонними так, чтобы это свойство сохранилось. Определите, возможно ли это, и если да — укажите направление каждой дороги.

Теорема Роббинса. Такая ориентация существует тогда и только тогда, когда граф связен и не имеет мостов. Мост очевидно мешает: сделав его односторонним, мы отрезаем одну половину графа от другой. Обратное — содержательная часть, и доказывается она построением.

Построение — обход в глубину. Древесные рёбра направляем вниз, от предка к потомку. Все остальные рёбра направляем вверх, от потомка к предку: в неориентированном графе перекрёстных рёбер не бывает, поэтому концы любого недревесного ребра связаны отношением «предок — потомок», и достаточно сравнить времена входа.

Почему получается сильная связность: вниз мы дойдём куда угодно по дереву, а вверх — потому что каждое древесное ребро не мост, значит из поддерева есть недревесное ребро наверх, и оно направлено к предку.

Ответ единственный: обход запускается из вершины 1, соседи перебираются по возрастанию номера, а при равенстве — по возрастанию номера ребра.

Первая строка содержит числа $n$ ($2 \le n \le 1000$) и $m$ ($1 \le m \le 10^5$).

Далее идут $m$ строк с дорогами. Петель нет, кратные дороги возможны; граф связен.

Если ориентации нет — одно число $0$.

Иначе $m$ строк: для каждой дороги в порядке ввода — откуда и куда по ней можно ехать.