401437: GYM100451 F Berland-Strike

A brand new Berland-Strike version 1.7 is released today! All Berland gamers rejoice and anticipate changes in the gameplay. And there are some! Unexpectedly for everyone game developers added puzzle elements into that classical shooter. Specifically, now if berrorists plant a bomb, counter-berrorists need to defuse it by solving a mini-puzzle.

The planted bomb has a sequence of n bridges attached. Each bridge has two contacts with which it is attached to the bomb. A contact is characterized by an integer number. Different contacts might be characterized by the same number, including if they belong to the same bridge. The first contact of the i-th bridge is numbered with x_i and the second — with y_i.

To solve the puzzle player can perform two actions. The first is reversing a bridge. The reverse action reverses contacts of the bridge, i.e. its first contact becomes its second one and its second contact becomes its first one. The second action is to swap any two bridges in the sequence. Player may reverse and swap any number of bridges. Each bridge could be reversed and swapped with other bridges many times.

The aim of the puzzle is to order the sequence of bridges so that the first contacts of bridges in the sequence are ordered in non-descending order while the second contacts must be ordered in non-ascending order.

For instance, assume that there are 4 bridges: (1, 5), (7, 1), (3, 8), (5, 6). After player reverses pairs 2, 3 and 4 the sequence looks as follows: (1, 5), (1, 7), (8, 3), (6, 5). Then player swaps pairs 1 and 2: (1, 7), (1, 5), (8, 3), (6, 5). And finally player swaps pairs 3 and 4: (1, 7), (1, 5), (6, 5), (8, 3). And that essentially solves the puzzle as the resulting sequence of the first contacts is non-descending: (1 ≤ 1 ≤ 6 ≤ 8) and the sequence of the second contacts is non-ascending: 7 ≥ 5 ≥ 5 ≥ 3.

Your task is to write a program which helps solving the puzzle. The bomb has been planted!

The first line of the input contains positive integer T — number of test cases in the input. Then follow T test cases.

The first line of each test case contains positive integer n (1 ≤ n ≤ 2·10⁵) — number of bridges in the test case. Each of the next n lines contains two integers x_i and y_i (0 ≤ x_i, y_i ≤ 10⁹).

Total number of bridges in all tests cases does not exceed 2·10⁵.

Output answer for each test case separately. On the first line print "yes" (without quotes) if there is a solution for the test case or "no" otherwise. If solution exists, on the next n lines print bridges in the required order. If there are multiple solutions print any of them.

2
4
1 5 
7 1 
3 8 
5 6
2
100 100
201 201

yes
1 7
1 5 
6 5
8 3
no