В Бертауне n перекрестков и m двусторонних дорог. Известно, что от любого перекрестка можно добраться до любого другого по существующим дорогам.
С ростом количества машин в городе возникла проблема пробок. Чтобы решить эту проблему, правительство решило сделать движение на всех дорогах односторонним, таким образом разгрузив движение. Ваша задача — определить, существует ли способ ввести одностороннее движение так, чтобы сохранилась возможность добраться от любого перекрестка до любого другого. В случае положительного ответа также требуется найти один из возможных способов ориентировать дороги.
Выходные данные
Если решения не существует, выведите одно число 0. Иначе выведите m строк по два целых числа pi и qi в каждой — ориентацию каждой дороги. То есть поток машин по односторонней дороге будет проходить в сторону от перекрестка pi к перекрестку qi. Дороги можно выводить в любом порядке. Если решений несколько, выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
6 7
1 2
2 3
1 3
4 5
4 6
5 6
2 4
|
0
|