CF1282E.The Cake Is a Lie

We are committed to the well being of all participants. Therefore, instead of the problem, we suggest you enjoy a piece of cake.

Uh oh. Somebody cut the cake. We told them to wait for you, but they did it anyway. There is still some left, though, if you hurry back. Of course, before you taste the cake, you thought about how the cake was cut.

It is known that the cake was originally a regular $n$-sided polygon, each vertex of which had a unique number from $1$ to $n$. The vertices were numbered in random order.

Each piece of the cake is a triangle. The cake was cut into $n - 2$ pieces as follows: each time one cut was made with a knife (from one vertex to another) such that exactly one triangular piece was separated from the current cake, and the rest continued to be a convex polygon. In other words, each time three consecutive vertices of the polygon were selected and the corresponding triangle was cut off.

A possible process of cutting the cake is presented in the picture below.

Example of 6-sided cake slicing.

You are given a set of $n-2$ triangular pieces in random order. The vertices of each piece are given in random order — clockwise or counterclockwise. Each piece is defined by three numbers — the numbers of the corresponding $n$-sided cake vertices.

For example, for the situation in the picture above, you could be given a set of pieces: $[3, 6, 5], [5, 2, 4], [5, 4, 6], [6, 3, 1]$.

You are interested in two questions.

• What was the enumeration of the $n$-sided cake vertices?
• In what order were the pieces cut?

Formally, you have to find two permutations $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$) and $q_1, q_2, \dots, q_{n - 2}$ ($1 \le q_i \le n - 2$) such that if the cake vertices are numbered with the numbers $p_1, p_2, \dots, p_n$ in order clockwise or counterclockwise, then when cutting pieces of the cake in the order $q_1, q_2, \dots, q_{n - 2}$ always cuts off a triangular piece so that the remaining part forms one convex polygon.

For example, in the picture above the answer permutations could be: $p=[2, 4, 6, 1, 3, 5]$ (or any of its cyclic shifts, or its reversal and after that any cyclic shift) and $q=[2, 4, 1, 3]$.

Write a program that, based on the given triangular pieces, finds any suitable permutations $p$ and $q$.

我们致力于保障所有参与者的身心健康。因此，我们建议您暂且放下这道题目，先享用一块蛋糕。

哎呀！有人把蛋糕切了。我们本已叮嘱他们等您回来再动手，但他们还是自作主张地切了。不过别担心，只要您赶紧回来，蛋糕还剩下一些。当然，在品尝蛋糕之前，您一定在思考蛋糕究竟是如何被切开的。

已知这块蛋糕原本是一个正 $n$ 边形，其每个顶点都被赋予了一个从 $1$ 到 $n$ 的唯一编号；这些顶点是按随机顺序编号的。

蛋糕的每一块均为三角形。整个切割过程将蛋糕分成了 $n - 2$ 块，具体方式如下：每次用刀沿一条顶点到另一顶点的连线进行一次切割，使得恰好分离出一个三角形块，而剩余部分仍保持为一个凸多边形。换言之，每次均选取当前多边形上三个连续的顶点，并将由它们构成的三角形切下。

下图展示了一种可能的蛋糕切割过程：

六边形蛋糕切割示例。

您现在被给定一组共 $n-2$ 个三角形块（以任意顺序给出），每个三角形块的三个顶点编号也以任意顺序（顺时针或逆时针）给出。每个三角形块由三个数字定义——即对应于原 $n$ 边形蛋糕的三个顶点编号。

例如，针对上图所示的情形，您可能收到如下三角形块集合：$[3, 6, 5], [5, 2, 4], [5, 4, 6], [6, 3, 1]$。

您关心以下两个问题：

• 原 $n$ 边形蛋糕的顶点编号顺序是怎样的？
• 各三角形块是按什么顺序被切下的？

形式化地说，您需要找出两个排列：$p_1, p_2, \dots, p_n$（其中 $1 \le p_i \le n$）和 $q_1, q_2, \dots, q_{n - 2}$（其中 $1 \le q_i \le n - 2$），使得若将蛋糕顶点按 $p_1, p_2, \dots, p_n$ 的顺序（顺时针或逆时针）编号，则按照 $q_1, q_2, \dots, q_{n - 2}$ 的顺序依次切下对应三角形块时，每次均能恰好分离出一个三角形，且剩余部分始终为一个凸多边形。

例如，在上图所示情形中，一种可行的排列为：$p=[2, 4, 6, 1, 3, 5]$（或其任意循环移位，或其反转后再任意循环移位），以及 $q=[2, 4, 1, 3]$。

请编写一个程序，根据所给的三角形块，找出任意一组满足条件的排列 $p$ 和 $q$。

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then there are $t$ independent sets of input data.

The first line of each set consists of a single integer $n$ ($3 \le n \le 10^5$) — the number of vertices in the cake.

The following $n - 2$ lines describe the numbers of the pieces vertices: each line consists of three different integers $a, b, c$ ($1 \le a, b, c \le n$) — the numbers of the pieces vertices of cake given in random order. The pieces are given in random order.

It is guaranteed that the answer to each of the tests exists. It is also guaranteed that the sum of $n$ for all test cases does not exceed $10^5$.

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。随后是 $t$ 组相互独立的输入数据。

每组数据的第一行包含一个整数 $n$（$3 \le n \le 10^5$），表示蛋糕的顶点数。

接下来的 $n - 2$ 行描述每块蛋糕片的顶点编号：每行包含三个互不相同的整数 $a, b, c$（$1 \le a, b, c \le n$），表示该蛋糕片的三个顶点编号，顺序任意。各蛋糕片以任意顺序给出。

保证每个测试用例均有解。同时保证所有测试用例的 $n$ 值之和不超过 $10^5$。

Print $2t$ lines — answers to given $t$ test cases in the order in which they are written in the input. Each answer should consist of $2$ lines.

In the first line of an answer on a test case print $n$ distinct numbers $p_1, p_2, \dots, p_n$($1 \le p_i \le n$) — the numbers of the cake vertices in clockwise or counterclockwise order.

In the second line of an answer on a test case print $n - 2$ distinct numbers $q_1, q_2, \dots, q_{n - 2}$($1 \le q_i \le n - 2$) — the order of cutting pieces of the cake. The number of a piece of the cake corresponds to its number in the input.

If there are several answers, print any. It is guaranteed that the answer to each of the tests exists.

输出 $2t$ 行——即按输入中给出的 $t$ 个测试用例的顺序，依次输出对应的答案。每个答案应包含 $2$ 行。

在每个测试用例答案的第一行中，输出 $n$ 个互不相同的整数 $p_1, p_2, \dots, p_n$（其中 $1 \le p_i \le n$），表示蛋糕顶点的编号，按顺时针或逆时针顺序排列。

在每个测试用例答案的第二行中，输出 $n - 2$ 个互不相同的整数 $q_1, q_2, \dots, q_{n - 2}$（其中 $1 \le q_i \le n - 2$），表示切割蛋糕各块的顺序。蛋糕块的编号与其在输入中的编号一致。

若存在多个合法答案，输出任意一个即可。保证每个测试用例均有解。