Bob got an undirected graph for his birthday! As part of his birthday present, he gets to direct the edges in his graph!
Bob hates triangles. He has decided to direct the edges of his graph such that there is a minimum number of triangles, but he's not sure how. Can you help him?
Note: A triangle is a set of distinct points such that the edges
,
and
all exist.
Input Specification
The first line will contain
and
separated by a space, the number of nodes and edges.
The next lines will contain
and
, an edge connecting
and
.
Output Specification
Output lines that contain
and
for each of the edges after directing them. The edges can be outputted in any order.
If there are multiple direction configurations that give a minimum number of triangles, you may output any of them.
Sample Input
5 4
1 2
4 3
3 2
1 3
Sample Output
1 2
3 2
4 3
3 1
Comments
A better question is, why would you get your kid a graph for his birthday?