Wielka Przesmycka 2011 Eternal

In a certain forest there are n meadows connected with paths. The meadows are numbered from 1 to n. Every path connects two distinct meadows; and between every two meadows there exists at most one path. Two paths may connect only on a meadow, meaning that they don't intersect. (However, they can lead through various underground tunnels, so you shouldn't assume that they could be drawn on a piece of paper without intersections.) It is possible to reach every meadow from every other meadow, possibly visiting other meadows on the way.

In this forest, biologists discovered two new species of ants: pink and yellow. The meadow number n contains the anthill of the pink ones, whereas the meadow number 1 contains the anthill of the yellow species. To make it easier to study their behaviour, the biologists decided to gather all the ants in their respective anthills (now the ants are scattered over all meadows). To this end, they synthesised a very strong directional pheromone for the pink ants. This kind of pheromone can be sprayed on any path p from meadow a to meadow b - then, the pink ants can walk along this path only in the direction from meadow a to meadow b. The biologists had just started celebrating the success when they realised that the pheromone for the pink ants also effects the yellow ants, but in the opposite direction! So, the yellow ants can only walk along the path p in the direction from meadow b to meadow a.

Now, the biologists are wondering whether it is possible to spray pheromone over all the paths (over every path in one suitable direction) so that for every meadow a, an ant beginning its travel on this meadow would have to eventually end up in its respective anthill regardless of its decisions made along the way. Additionally, after returning to the anthill, the ant must not be able to leave it. In particular, this rule means that an ant should be able to leave every meadow using some path (except the meadow containing its respective anthill). It also means that an ant must not be able to visit the same meadow twice during its travel (because otherwise it could decide to walk in a loop infinitely).

Multiple test cases

The first line of the input contains Z ≤ 30000 - the number of test cases. Z descriptions of single test cases follow. The overall input size will be several dozen megabytes.

Single test case

The first line of the input contains two space-separated integers n and m - the number of meadows and paths, respectively. The following m lines contain two distinct integers a_i and $b_i each denoting a path between meadows a_i and b_i.

Bounds

Common: 2 ≤ n ≤ 250000, 1 ≤ m ≤ 500000

Output

Basic: if it is possible to spray every path with pheromone in a suitable direction in a way that satisfies the problem statement, then the only line of the output should contain the word YES. Otherwise, print NO.

Professional: Output the first row as in the basic version. Additionally, if the answer is YES, print m lines describing all the paths (not necessarily in the same order as in the input). Printing a_i b_i (space-separated) should denote spraying the path with pheromone in the direction from meadow a_i to meadow b_i. If there are many solutions, print any of them.

Sample input

2
7 9
1 2
2 3
3 4
4 1
3 7
5 2
5 7
6 4
6 7
7 8
1 2
2 3
3 4
4 2
2 5
5 6
6 2
2 7

Sample output

TAK
1 2
2 5
5 7
1 4
4 6
6 7
2 3
4 3
3 7
NIE