Closing the Circuit

Hektor, uneasy about his future in the job market, decides to learn how to build electronic assemblies. He starts by closing an electrical circuit on a flat, two-dimensional board.

A power line runs across the middle of the board. On it sit $n$ connectors, numbered $1$ to $n$ from left to right. The power line splits the board into an upper half and a lower half. Wires are already installed on the upper half, and they satisfy all of the following rules.

• Each wire joins exactly two connectors.
• No two wires cross or touch each other.
• Every connector is attached to exactly one wire.
• No wire crosses the power line.

In other words, the upper wires form a set of non-crossing arcs above the power line, that is, a non-crossing perfect matching.

Hektor wants to close the circuit so that, following wires, one can travel from any connector to every other connector. To do this he will add wires on the lower half of the board. The new wires must obey the same rules as the upper ones: each new wire joins two connectors, the new wires do not cross or touch one another, every connector is attached to exactly one new wire, and no new wire crosses the power line.

Because the upper wires already form a valid non-crossing layout, a lower layout that makes every connector reachable from every other always exists. Find and output one such layout.

The first line contains an integer $t$, the number of test sets ($1 \le t \le 10$). The test sets follow, one after another.

The first line of each test set contains an even integer $n$ ($2 \le n \le 10^6$), the number of connectors on the power line. Each of the next $n/2$ lines contains two integers $a$, $b$, meaning that connectors $a$ and $b$ are joined by a wire on the upper half of the board.

Many lower layouts may work, so to make the answer unique output the following canonical layout. Treat the power line as cyclic, so the connector after $n$ is connector $1$. For an upper wire joining connectors $a$ and $b$, add the lower wire joining the connectors that come immediately after them. In formula form, the upper wire $(a, b)$ produces the lower wire $((a \bmod n) + 1,\ (b \bmod n) + 1)$.

For each test set, first print TAK (Polish for "yes") on its own line. Then print the $n/2$ lower wires, each as two connector numbers with the smaller one first, listing the wires in increasing order of their first connector.