There were N cities in Far Far Away, some of which were connected by roads. Unfortunately, recently it has become very difficult to get from one city to another due to traffic jams. In order to combat traffic jams, it was decided to make all roads one-way, i. allow travel on each road in only one direction. At the same time, it is required that it is still possible to get from any city to any other.
Input
The input file contains first the number N — number of cities (1≤N≤1000). Then the number M — number of roads (1≤M≤100000). Then there are M pairs of numbers defining the roads (each road is described by the numbers of the cities it connects). There are no roads from some city to the same city. There can be several roads between two cities. It is guaranteed that before the introduction of one-way traffic it was possible to get from any city to any other.
Imprint
The output file should contain M pairs of numbers corresponding to the roads (the roads should be output in the same order as they are given in the input file). For each road, the number of the city from which it will be possible to leave after the introduction of one-way traffic must first be recorded, and then — the number of the city where this road leads.
If you enter one-way traffic so that you can get from any city to any other, it is impossible, the output file should contain a single number 0.
Examples
| # |
Input |
Output |
| 1 |
4
6
1 2
1 2
23
24
4 3
14 |
2 1
2 1
3 2
4 2
4 3
14 |