Connections

Hard times have come to Byteland. Quantum computing is going mainstream and Qubitland is about to occupy Byteland. Byteland does not have enough money for this war, so its king, Byteman 0x0B, decided to reform the road system and cut expenses.

Byteland has $n$ cities connected by $m$ one way roads, and these roads let you travel from any city to any other city. No two roads cross outside the cities, and no other roads exist. The roads are one way because each of them carries a barrier halfway that opens in one direction only. The barriers are there to make enemies waste time when they pick the wrong way.

The reform abandons some of the roads so that exactly $2n$ roads remain. The king's advisers think $2n$ roads are enough to keep the ability to travel from any city to any other city. Whether fewer roads would also be enough, they do not know. What is left is choosing which roads to abandon.

The input holds several test cases. The first line contains the number of test cases.

The first line of each test case contains $n$ and $m$, the number of cities and the number of roads ($n \ge 4$, $m > 2n$). Each of the next $m$ lines contains two integers $x_i$ and $y_i$ describing a road from city $x_i$ to city $y_i$ ($1 \le x_i, y_i \le n$, $x_i \ne y_i$). The given roads are guaranteed to let you travel from any city to any other city. For every pair of cities $x$ and $y$ there is at most one road from $x$ to $y$ and at most one road from $y$ to $x$. An answer always exists. The sum of $m$ over all test cases in one input is at most 100,000.

For each test case print exactly $m - 2n$ lines. Each line holds the source city and the destination city of one abandoned road, separated by a single space.

Many sets of roads can be abandoned, so only the set produced by the following rule counts as correct. Inside one test case, number the roads from 1 to $m$ in the order they are given.

1. Run a breadth first search from city 1 that follows the roads in their given direction. At the start mark only city 1 as visited and put it in a first in first out queue. Take a city $u$ out of the queue and look at the roads that leave $u$ in increasing order of road number. If such a road ends at a city that is not visited yet, mark that city as visited, put it in the queue, and keep the road. Call the set of roads kept this way $A$.
2. Run the same breadth first search from city 1 on the graph with every road reversed. For a city $u$ taken out of the queue, look at the roads that enter $u$ in increasing order of road number, and if such a road starts at a city that is not visited yet, mark that city as visited, put it in the queue, and keep the road. Call the set of roads kept this way $B$.
3. Let $K = A \cup B$. The set $K$ holds at most $2n - 2$ roads, so add the roads outside $K$ to it in increasing order of road number until $K$ holds exactly $2n$ roads.
4. Abandon every road that did not end up in $K$, and print those roads in increasing order of road number.