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 ~(a, b, c)~ such that the edges ~(a, b)~, ~(b, c)~ and ~(c, a)~ all exist.
The first line will contain ~N~ ~(1 \le N \le 2 \times 10^5)~ and ~M~ ~(1 \le M \le 2 \times 10^5)~ separated by a space, the number of nodes and edges.
The next ~M~ lines will contain ~u~ and ~v~ ~(1 \le u, v \le N, u \ne v)~, a directed edge connecting ~u~ and ~v~.
Output ~M~ lines that contain ~u~ and ~v~ 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.
5 4 1 2 4 3 3 2 1 3
1 2 3 2 4 3 3 1