В Тридевятом Царстве было N городов, некоторые из которых были соединены дорогами. К сожалению, в последнее время добраться из одного города в другой стало очень сложно из-за возникших автомобильных пробок. В целях борьбы с пробками было решено все дороги сделать односторонними, т.е. разрешить проезд по каждой дороге только в одном направлении. При этом требуется, чтобы по-прежнему можно было из любого города попасть в любой другой.
Входные данные
Во входном файле записано сначала число N — количество городов (1≤N≤1000). Затем записано число M — количество дорог (1≤M≤100000). Далее идет M пар чисел, задающих дороги (каждая дорога описывается номерами городов, которые она соединяет). Не бывает дорог из некоторого города в тот же город. Между двумя городами может быть несколько дорог. Гарантируется, что до введения одностороннего движения можно было попасть из любого города в любой другой.
Выходные данные
В выходной файл нужно выдать M пар чисел, соответствующих дорогам (дороги должны быть выданы в том же порядке, в котором они заданы во входном файле). Для каждой дороги сначала должен быть записан номер города, из которого по ней можно будет уехать после введения одностороннего движения, а затем — номер города, куда эта дорога ведет.
Если ввести одностороннее движение так, чтобы можно было из любого города попасть в любой другой, нельзя, выходные данные содержать одно число 0.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4
6
1 2
1 2
2 3
2 4
4 3
1 4 |
2 1
2 1
3 2
4 2
4 3
1 4 |