#640 Two Trees

Loading problem...

Preparing the statement, recent submissions, and submit form.

#640 Two Trees

DOJ/Grand Contest DOJ/GCD 1/Div2

Authors: pk661

Time limit: 1000 ms
Memory limit: 1024 MB
Checker: CUSTOM
Solve threshold: 100

Statement

Statement language

You are given a tree $T_1$ with $N$ vertices numbered $1,2,\cdots,N$ .

For two trees $T_1,T_2$ on the same vertices, we say that they are in a good relationship if there is no set of vertices $S$ satisfying both of the following conditions.

$2\le |S|\le N-1$ .
The subgraphs induced by $S$ in $T_1$ and are both connected.

Definition of an induced subgraph

The subgraph induced by a set of vertices $S$ is obtained by keeping exactly the vertices in $S$ and all edges whose two endpoints both belong to $S$ .

Determine whether there exists a tree $T_2$ in a good relationship with $T_1$ , and construct one if it exists.

Input

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the answer as follows.

If no valid $T_2$ exists, print $-1$ on one line.

Otherwise, print $N-1$ lines in the following format:

Constraints

$1\le T\le 50\,000$ .
$3\le N\le 200\,000$ .
$1 \leq U_{}$ ().

Subtasks

#	Score	Constraints
1	9	The sum of $N$ over all test cases does not exceed $7$ .
2	31	The sum of $N$ over all test cases does not exceed $2\,000$ .
3	12	().

Samples

Input

Output

Editorial

View editorial

P_{1} Q_{1}

P_1\ Q_1

i

,

V_{i}

\leq

N

1\le U_i,V_i\le N

U_{i}

=

i

,

V_{i}

=

i

+

1

U_i=i,\ V_i=i+1