E. Дороги в Бертауне
ограничение по времени на тест
5 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

В Бертауне n перекрестков и m двусторонних дорог. Известно, что от любого перекрестка можно добраться до любого другого по существующим дорогам.

С ростом количества машин в городе возникла проблема пробок. Чтобы решить эту проблему, правительство решило сделать движение на всех дорогах односторонним, таким образом разгрузив движение. Ваша задача — определить, существует ли способ ввести одностороннее движение так, чтобы сохранилась возможность добраться от любого перекрестка до любого другого. В случае положительного ответа также требуется найти один из возможных способов ориентировать дороги.

Входные данные

В первой строке через пробел записаны два целых числа n и m (2 ≤ n ≤ 105, n - 1 ≤ m ≤ 3·105) — количество перекрестков и дорог в городе соответственно. Далее следует m строк по два числа в каждой — описание дорог в городе. Каждая дорога задается двумя целыми числами ai и bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — номерами перекрестков, которые она соединяет.

Гарантируется, что от каждого перекрестка можно добраться до любого другого по имеющимся двусторонним дорогам. Каждая дорога соединяет различные перекрестки, между каждой парой перекрестков существует не более одной дороги.

Выходные данные

Если решения не существует, выведите одно число 0. Иначе выведите m строк по два целых числа pi и qi в каждой — ориентацию каждой дороги. То есть поток машин по односторонней дороге будет проходить в сторону от перекрестка pi к перекрестку qi. Дороги можно выводить в любом порядке. Если решений несколько, выведите любое.

Примеры
Входные данные
6 8
1 2
2 3
1 3
4 5
4 6
5 6
2 4
3 5
Выходные данные
1 2
2 3
3 1
4 5
5 6
6 4
4 2
3 5
Входные данные
6 7
1 2
2 3
1 3
4 5
4 6
5 6
2 4
Выходные данные
0