You are given a tree with vertices numbered .
For two trees on the same vertices, we say that they are in a good relationship if there is no set of vertices satisfying both of the following conditions.
Definition of an induced subgraph
The subgraph induced by a set of vertices is obtained by keeping exactly the vertices in and all edges whose two endpoints both belong to .
Determine whether there exists a tree in a good relationship with , and construct one if it exists.
The input is given from Standard Input in the following format:
For each test case, print the answer as follows.
If no valid exists, print on one line.
Otherwise, print lines in the following format:
Each test case is given in the following format:
The -th edge of connects vertices and .
The printed edges must form a tree on vertices , and and must be in a good relationship.
If there are multiple solutions, print any of them.
| 4 | 48 | No additional constraints. |