Constructing a Domination Tree

You are given n visitors numbered from 1 to n who are attending a banquet. You must assign a domination relationship among them according to the following rules:

• Exactly one visitor becomes the overall dominator (the root), who directly controls the remaining n-1 visitors.
• Every other visitor has exactly one direct dominator; the set of direct domination relations forms a rooted tree.
• If visitor a is directly dominated by visitor b, we say b dominates a. Domination is transitive: if a dominates b and b dominates c, then a also dominates c.

There are also m domination conditions. Each condition is represented as an ordered pair \((x,y)\) (with \(1 \le x,y \le n\) and \(x\ne y\)). For a condition \((x,y)\):

• If x dominates y (i.e. x is an ancestor of y in the tree), the shadow power increases by 1.
• If y dominates x, the shadow power decreases by 1.
• If neither dominates the other then the shadow power is unchanged.

The initial shadow power is 0, and your task is to construct a domination tree such that the final shadow power is non-negative. If there are multiple solutions, output any one. It is guaranteed that for any valid input, a solution exists.

Hint: One simple solution is to choose a visitor r as the root such that the number of conditions where r appears as the first element is at least the number of conditions where r appears as the second element. Then, by making r the root and having it directly dominate every other visitor (i.e. a star tree), the overall shadow power becomes \(A[r]-B[r]\), which is non-negative.

inputFormat

The first line contains two integers n and m separated by a space. Each of the following m lines contains two integers x and y, representing a domination condition ((x,y)).

outputFormat

Output n-1 lines. Each line should contain two integers u and v separated by a space, meaning that visitor u directly dominates visitor v. The constructed tree must ensure that the overall shadow power is non-negative.

sample

3 2
1 2
2 3

1 2
1 3