B. Galician Roads
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In a certain region of Galicia, there are $$$n$$$ towns, and there are $$$m$$$ two-way roads connecting some pairs of towns, such that it is possible to travel from any town to another by car.

Due to a change in the law, all roads in the region must become one-way. The Galicians have asked for your help in modifying their road system. For each existing road, the Galicians allow you to decide the direction that the road will take. Additionally, if necessary, you can build new one-way roads.

The Galicians want to ensure that it is still possible to travel by car between any pair of towns, but they ask you to build the minimum number of new roads possible. Furthermore, since you are very skilled, the Galicians want to ask for your help in fixing the road systems of $$$T$$$ different regions. Can you help them?

Input

The first line contains a positive integer $$$T$$$, the number of regions in Galicia to process.

Each case starts with two positive integers $$$n$$$ and $$$m$$$, the number of towns and roads in the region, respectively. The towns are numbered $$$1,2,3,\dots,n$$$.

This is followed by $$$m$$$ lines, each containing two integers $$$1\le u_i, v_i\le n$$$, the towns connected by the $$$i$$$-th road in the region. It is guaranteed that $$$u_i \ne v_i$$$ for all $$$i$$$, and that there are no two roads connecting the same pair of towns.

Output

For each case, you must print the following. The first line should contain the minimum number $$$M$$$ of roads that need to be built.

The following $$$M+m$$$ lines should contain your road project. This includes both the added roads and the already existing roads oriented as you wish. Formally, the $$$i$$$-th line should contain two integers $$$1\le u_i, v_i\le n$$$, representing a one-way road from town $$$u_i$$$ to town $$$v_i$$$.

Note that you are allowed to connect a pair of distinct towns with more than one road.

Scoring
  1. (8 points) In each region, there are exactly $$$m = n-1$$$ roads, and there is one town that is the endpoint of all roads.
  2. (70 points) In each region, there are exactly $$$m = n-1$$$ roads.
  3. (12 points) The sum of $$$m^2$$$ over all cases does not exceed $$$10^6$$$.
  4. (10 points) No additional restrictions.
Example
Input
2
3 3
1 2
1 3
2 3
3 2
1 2
1 3
Output
0
3 1
2 3
1 2
1
1 2
3 1
2 3
Note

$$$1 \le T \le 1000$$$

$$$2 \le n \le 2\cdot 10^5$$$

$$$1 \le m \le 2\cdot 10^5$$$

The sum of $$$m$$$ over all cases does not exceed $$$2\cdot 10^5$$$.