The Cake Is a Lie

题意翻译

二维平面上有一个正 $n$ 边形，顶点用 $1$ 至 $n$ 中的正整数乱序编号，但保证不同顶点的编号一定不同。 现在给出这个 $n$ 边形的一种三角剖分的可行方案（注意：这意味着将给出 $n-2$ 个三角形的顶点信息）。你需要求出： - 这个$n$边形顶点编号的排列顺序$p$； - 各个三角形被切下去的顺序$q$。 如果有多解输出任意一组。 **输入格式** 注意：**每个测试点中有多组测试数据**。第一行一个正整数 $t(1\leq t\leq 10^3)$ 表示数据组数。 接下来将有 $t$ 组测试数据。每组数据第一行一个正整数 $n(3\leq n\leq 10^5)$ 表示多边形的边数。接下来$n-2$行，每行三个正整数 $a,b,c(1\leq a,b,c\leq n)$ ，描述一个三角形。 请注意：输入中所有的三角形都可能是乱序给出的，每个三角形内的三个点也可能是按顺时针或逆时针方向给出的。输入数据保证存在至少一种方案。 **输出格式** 输出 $2t$ 行。对于每组测试数据输出两行： - 第一行包含一个 $1$ 至 $n$ 的排列 $p$ ，顺次描述多边形的各个顶点。注意：可以以任意点为起点、按任意方向输出，若有多解任意输出一种即可。 - 第二行包含一个 $1$ 至 $n-2$ 的排列 $q$ ，顺次描述切下的每个三角形的编号。请输出能够对应节点编号 $p$ 的解。若有多解输出任意一组。注意：为了方便，三角形按输入给出的顺序编号，第 $i$ 个输入的三角形的编号即为 $i$ 。 注意：输出每个排列的时候，相邻两个正整数间请空一格。

题目描述

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 $ .

输入输出格式

输入格式

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 $ .

输出格式

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.

输入输出样例

输入样例 #1

3
6
3 6 5
5 2 4
5 4 6
6 3 1
6
2 5 6
2 5 1
4 1 2
1 3 5
3
1 2 3

输出样例 #1

1 6 4 2 5 3 
4 2 3 1 
1 4 2 6 5 3 
3 4 2 1 
1 3 2 
1 

题意翻译

二维平面上有一个正 $n$ 边形，顶点用 $1$ 至 $n$ 中的正整数乱序编号，但保证不同顶点的编号一定不同。 现在给出这个 $n$ 边形的一种三角剖分的可行方案（注意：这意味着将给出 $n-2$ 个三角形的顶点信息）。你需要求出： - 这个$n$边形顶点编号的排列顺序$p$； - 各个三角形被切下去的顺序$q$。 如果有多解输出任意一组。 **输入格式** 注意：**每个测试点中有多组测试数据**。第一行一个正整数 $t(1\leq t\leq 10^3)$ 表示数据组数。 接下来将有 $t$ 组测试数据。每组数据第一行一个正整数 $n(3\leq n\leq 10^5)$ 表示多边形的边数。接下来$n-2$行，每行三个正整数 $a,b,c(1\leq a,b,c\leq n)$ ，描述一个三角形。 请注意：输入中所有的三角形都可能是乱序给出的，每个三角形内的三个点也可能是按顺时针或逆时针方向给出的。输入数据保证存在至少一种方案。 **输出格式** 输出 $2t$ 行。对于每组测试数据输出两行： - 第一行包含一个 $1$ 至 $n$ 的排列 $p$ ，顺次描述多边形的各个顶点。注意：可以以任意点为起点、按任意方向输出，若有多解任意输出一种即可。 - 第二行包含一个 $1$ 至 $n-2$ 的排列 $q$ ，顺次描述切下的每个三角形的编号。请输出能够对应节点编号 $p$ 的解。若有多解输出任意一组。注意：为了方便，三角形按输入给出的顺序编号，第 $i$ 个输入的三角形的编号即为 $i$ 。 注意：输出每个排列的时候，相邻两个正整数间请空一格。