我们致力于所有参与者的福祉。因此,与其解决问题,我们建议您享受一块蛋糕。
呃哦。有人切蛋糕了。我们告诉他们要等你,但他们还是这么做了。不过,如果你快点回来的话,还剩下一些。当然,在品尝蛋糕之前,你会想到蛋糕是如何切的。
众所周知,蛋糕最初是一个规则的$$$n$$$边多边形,每个顶点都有一个从$$$1$$$到$$$n$$$的唯一编号。顶点按随机顺序编号。
每块蛋糕都是一个三角形。将蛋糕切成 $$$n - 2$$$ 块,如下:每次用刀切一次(从一个顶点到另一个顶点),使得正好从当前蛋糕中分离出一个三角形块,其余部分继续为凸多边形。也就是说,每次选择多边形的三个连续顶点,并切掉对应的三角形。
下图展示了切蛋糕的可能过程。
6 面蛋糕切片示例。
给你一组随机排列的 $$$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$$$。
输入
第一行包含一个整数 $$$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$$$。
输出
打印 $$$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$$$) - 切蛋糕的顺序。一块蛋糕的数量与输入中的数量相对应。
如果有多个答案,请打印其中一个。保证每个测试的答案都存在。
示例
输入 #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