← 返回题目列表

Codeforces · 1255/C

C. 莱森联盟

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

Bob是电子游戏“League of Leesins”的狂热粉丝,今天他庆祝Leesins联盟世界冠军赛落下帷幕!

The tournament consisted of $$$n$$$ ($$$n \ge 5$$$) teams around the world. Before the tournament starts, Bob has made a prediction of the rankings of each team, from $$$1$$$-st to $$$n$$$-th.决赛结束后,他将预测与实际结果进行比较,发现按照他预测的第$$$i$$$队伍最终获得了第$$$p_i$$$位置($$$1 \le p_i \le n$$$,所有$$$p_i$$$都是唯一的)。 In other words, $$$p$$$ is a permutation of $$$1, 2, \dots, n$$$.

由于 Bob 最喜欢的联盟玩家是著名的“3ga”,他决定写下排列 $$$p$$$ 的每个 $$$3$$$ 连续元素。 Formally, Bob created an array $$$q$$$ of $$$n-2$$$ triples, where $$$q_i = (p_i, p_{i+1}, p_{i+2})$$$ for each $$$1 \le i \le n-2$$$. Bob was very proud of his array, so he showed it to his friend Alice.

在得知 Bob 的数组后,Alice 声明即使 Bob 重新排列 $$$q$$$ 的元素以及每个三元组中的元素,她也可以检索排列 $$$p$$$。 Of course, Bob did not believe in such magic, so he did just the same as above to see Alice's respond.

例如,如果 $$$n = 5$$$ 且 $$$p = [1, 4, 2, 3, 5]$$$,则原始数组 $$$q$$$ 将为 $$$[(1, 4, 2), (4, 2, 3), (2, 3, 5)]$$$。 Bob can then rearrange the numbers within each triple and the positions of the triples to get $$$[(4, 3, 2), (2, 3, 5), (4, 1, 2)]$$$.请注意 $$$[(1, 4, 2), (4, 2, 2), (3, 3, 5)]$$$ 不是 $$$q$$$ 的有效重新排列,因为不允许 Bob 交换属于不同三元组的数字。

作为 Alice 的朋友,您肯定知道 Alice 只是想炫耀,因此您决定给她提供与她所得到的数组 $$$q$$$ 一致的任何排列 $$$p$$$ 来给她留点面子。

输入

The first line contains a single integer $$$n$$$ ($$$5 \le n \le 10^5$$$) — the size of permutation $$$p$$$.

接下来的 $$$n-2$$$ 行中的第 $$$i$$$ 包含 $$$3$$$ 整数 $$$q_{i, 1}$$$, $$$q_{i, 2}$$$, $$$q_{i, 3}$$$ ($$$1 \le q_{i, j} \le n$$$) - 的元素 $$$i$$$-th triple of the rearranged (shuffled) array $$$q_i$$$, in random order. Remember, that the numbers within each triple can be rearranged and also the positions of the triples can be rearranged.

It is guaranteed that there is at least one permutation $$$p$$$ that is consistent with the input.

输出

打印 $$$n$$$ 不同的整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) 使得 $$$p$$$ 与数组 $$$q$$$ 一致。

如果有多个答案,请打印其中一个。

示例

输入 #1

5
4 3 2
2 3 5
4 1 2

输出 #1

1 4 2 3 5