One-Way Roads

The ACM kingdom has $N$ cities joined by $M$ two-way roads. The road network is connected, so you can travel from any city to any other city along the roads. The government wants to make every road one-way. After the directions are fixed, it must still be possible to travel from any city to any other city. Decide whether such an assignment exists, and print the one described in the output section when it does.

The first line contains $T$ ($0 \le T \le 100$), the number of test cases.

The first line of each test case contains two integers $N$ ($1 \le N \le 50$) and $M$ ($1 \le M \le N(N-1)/2$). Each of the next $M$ lines contains two integers $X$ and $Y$ ($1 \le X, Y \le N$, $X \ne Y$), a road between city $X$ and city $Y$. At most one road joins a given pair of cities, and the road network of every test case is connected.

For each test case, print NO on a single line when no assignment works. Otherwise print YES on the first line, then $M$ lines that give the direction of each road. Line $i$ holds the start city and then the end city of the $i$-th road of the input.

Several assignments can work, so exactly one of them counts as correct. Build it like this. Run a depth-first search that starts at city 1. When the search leaves a city it moves to the unvisited neighboring city with the smallest number, and it backtracks once every neighbor of the current city is already visited. A road that the search uses to reach a city for the first time is directed from the city the search left towards the city it reached. Every other road is directed from the endpoint that the search visited later towards the endpoint that the search visited earlier. If any assignment keeps the kingdom fully connected, this one does.