Road Reform

Hard times are coming to Byteland. In order to reduce expenses for the impending war against Qubitland, King Byteman $0x0B$ has decided to reform the road system. Byteland is represented by a strongly connected directed graph with n cities and m one‐way roads. Each road has a one-way halfway barrier, so the roads are directed. It is guaranteed that there is a path from any city to any other city.

The idea is to abandon some roads such that exactly $2n$ roads remain, while still keeping the network strongly connected. One known approach is to find a spanning tree (an out‐branching rooted at city 1) from the original graph and a spanning tree of the reverse graph (an in‐branching rooted at city 1) and then add extra roads if necessary.

Your task is to select exactly $2n$ roads from the given road network so that the remaining network is strongly connected. You may assume that a solution always exists.

inputFormat

The first line of input contains two integers $n$ and $m$ --- the number of cities and roads, respectively. Each of the following $m$ lines contains two integers $u$ and $v$ indicating a one-way road from city $u$ to city $v$.

outputFormat

Output exactly $2n$ lines. Each line should contain two integers $u$ and $v$ representing a road that remains after the reform. The selected roads must guarantee that the road network remains strongly connected.

sample

3 6
1 2
2 3
3 1
1 3
2 1
3 2

1 2
2 3
3 1
1 3
2 1
3 2