Triangulation

Task

Little Polygon received a gift from his wonderful friend Little Circle. In the gift there was a drawing of an $N$ vertex polygon, each vertex being labeled with an integer from $1$ to $N$, and a triangulation of it, e.g:

There was also a note, which asked Little Polygon to write every number from $2$ to $N - 1$ once, one number inside each triangle, so that number $i$ is written in a triangle that has vertex $i$ as a corner. For example:

Note that every number from $2$ to $N - 1$ has been written exactly once. Furthermore, each number $i$ is in a triangle which has $i$ as a vertex:

Help Little Polygon find a way of writing these numbers inside the triangles, as well as counting how many ways of doing this there are.

Input data

Each input file will contain multiple test cases.
The first line of the input contains $T$, the number of test cases.
Each test case begins with a line containing $N$, the number of sides of the input polygon. The second line contains labels of the vertices of the polygon, in counter-clockwise order. The next $N - 2$ lines each contain a triple, representing the vertices of a triangle in the triangulation.

Output data

Output two lines for each test case. On the first line, output a valid way of writing numbers in the triangles (output the numbers in the same order as the triangles in the input file). On the second line, output how many ways there are of doing this, modulo $10^9 + 7$.

Constraints and clarifications

• If only the first line of the output for every test case in an output file is correct, you will receive $50\%$ of the score for that file. If only the second line of the output for every test case in an output file is correct, you will also receive $50\%$ of the score for that file. If the entire file is correct, you will receive $100\%$ of the score for that file.
• Note! Output two lines for each test case, the first containing $N - 2$ integers, the second containing one integer, all of which can be represented as int-type variables, even if one of the lines is wrong. Otherwise you will receive the evaluation judgment Invalid output format.
• $1 \leq T \leq 50 \ 000$.
• $3 \leq N \leq 50 \ 000$.
• The sum of $N$ over all test cases in one file is at most $50 \ 000$
• The triangles given in any test case form a valid triangulation.

Example

stdin

1
12
1 2 6 7 4 8 10 12 5 9 11 3
11 5 9
1 7 11
10 5 12
1 2 7
6 7 2
3 11 1
11 10 8
11 10 5
4 8 11
7 4 11

stdout

9 11 10 2 6 3 8 5 4 7
9

Explanation

This is the example drawn above in the statement.