ml2 | Connect the Dots

As a pastime, Luca likes to play “Connect the dots”, a game that requires you to connect all the given points with a line, effectively revealing a figure’s outline.

While looking at the lines that connect the dots, Luca is wondering what would happen if those had an arrow (i.e., they would not only just connect two dots, but they would always have a direction). Even though it is entirely useless for the game, Luca is nonetheless curious about the potential reveal of some interesting patterns.

When the arrows are added in certain ways, some dots might become stars: either all the connections in which they are involved have an arrow that starts from them and leads elsewhere, or they all point towards that dot.

Here is an example: the left figure is the original one, the middle and the right ones are the result of two out of the many ways to add arrows. The dots highlighted in red and blue are two examples of, respectively, the former and the latter kind of stars.

Can you come up with a way to add an arrow to (i.e, direct) every connection between two dots such that the result does not contain any star?

Input data

The first line contains two integers $N$ and $M$, respectively the number of dots and the number of connections between them. The following $M$ lines contain two integers $A_i$ and $B_i$ each, indicating that the two dots are connected with a line.

Output data

You need to write $M$ lines, each containing two integers $S_i$, $E_i$ to indicate a directed arrow starting from $S_i$ and ending in $E_i$. You can print the lines in any order.

Constraints and clarifications

• $2 \leq N \leq 10 \ 000$;
• $1 \leq M \leq 100 \ 000$;
• $0 \leq A_i, B_i < N$, $A_i \neq B_i$;
• Each dot is connected to at least one line.
• It is guaranteed that at least one solution exists. In case of multiple solutions, you can output any.

Example 1

stdin

4 4
1 0
3 1
2 3
2 0

stdout

0 1
1 3
3 2
2 0

Explanation

The following is a possible solution for the first sample case:

Example 2

stdin

5 7
0 1
1 2
0 3
3 1
3 2
3 4
4 2

stdout

0 1
1 2
2 3
2 4
3 0
3 1
4 3

Explanation

The second sample case corresponds to the one described earlier in the statement. The solution avoids the formation of any kind of star.