34773번 - Expansion of the road network 스페셜 저지다국어

문제

Legend has it that, long ago, the Service of Braveway Connections (SBC) administered a network of bidirectional roads that connected various cities. At that time, the layout was extremely simple: between any two cities there was exactly one path.

With population growth and increased transportation of goods, the Institute of Connected and Planned Cities (ICPC) took control and decided to modernize the network. To avoid internal traffic in intermediate cities and speed up travel, new direct roads were built between certain pairs of cities. A new road was created between two cities $A$ and $B$ whenever, in the original layout, the path between them passed through exactly one intermediate city.

Today, we only have the current map of the network, and ICPC wants to find out whether it could indeed have arisen from this process.

Your task is to analyze the current map and determine whether the legend could be true. If possible, you should also reconstruct and print a possible original layout of the network.

입력

The first line contains two integers $N$ and $M$ (3ドル ≤ N ≤ 10^5,ドル 2ドル ≤ M ≤ 4 \times 10^5$), representing, respectively, the number of cities and the number of roads in the current map.

Each of the following $M$ lines contains two integers $u_i$ and $v_i$ (1ドル ≤ u_i , v_i ≤ N,ドル $u_i \ne v_i$), indicating that there is a bidirectional road between cities $u_i$ and $v_i$. In the current map, it is guaranteed that there is a path between any pair of cities and that there is at most one road between any pair of cities.

출력

If the current map could have arisen from the process described in the legend, the output should contain $N −1$ lines. Each line should contain two integers $a_i$ and $b_i$ (1ドル ≤ a_i , b_i ≤ N,ドル $a_i \ne b_i$), indicating that there was a direct road between cities $a_i$ and $b_i$ in the original layout.

Otherwise, the output should contain only one line with a single character “*” (asterisk).

If there is more than one possible original layout, print any of them.

제한

노트