← 返回题目列表

Codeforces · 1282/E

E. 蛋糕是一个谎言

中文机器翻译题面 查看原题

我们致力于所有参与者的福祉。因此,与其解决问题,我们建议您享受一块蛋糕。

呃哦。有人切蛋糕了。我们告诉他们要等你,但他们还是这么做了。不过,如果你快点回来的话,还剩下一些。当然,在品尝蛋糕之前,你会想到蛋糕是如何切的。

众所周知,蛋糕最初是一个规则的$$$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