CF1255C League of Leesins

Bob 是《League of Leesins》这款电子游戏的忠实粉丝，今天他正在庆祝 League of Leesins 世界锦标赛的圆满结束！ 本次比赛共有 $n$ 支来自世界各地的队伍（$n \ge 5$）。在比赛开始前，Bob 预测了每支队伍的排名，从第 $1$ 名到第 $n$ 名。比赛结束后，他将自己的预测与实际结果进行了对比，发现他预测的第 $i$ 支队伍最终获得了第 $p_i$ 名（$1 \le p_i \le n$，所有 $p_i$ 互不相同）。换句话说，$p$ 是 $1, 2, \dots, n$ 的一个排列。 由于 Bob 最喜欢的选手是著名的“3ga”，他决定把排列 $p$ 中每 $3$ 个连续元素都记录下来。具体来说，Bob 构造了一个长度为 $n-2$ 的三元组数组 $q$，其中 $q_i = (p_i, p_{i+1}, p_{i+2})$，对于每个 $1 \le i \le n-2$。Bob 对自己的数组非常自豪，于是把它展示给了他的朋友 Alice。 Alice 得知 Bob 的数组后，声称即使 Bob 把 $q$ 中每个三元组内部的元素顺序打乱，并且把所有三元组的位置也打乱，她依然能够还原出排列 $p$。当然，Bob 并不相信这种“魔法”，于是他就按上述方式对 $q$ 进行了打乱，看看 Alice 会如何应对。 例如，如果 $n = 5$ 且 $p = [1, 4, 2, 3, 5]$，则原始数组 $q$ 为 $[(1, 4, 2), (4, 2, 3), (2, 3, 5)]$。Bob 可以将每个三元组内部的数字顺序打乱，并且打乱三元组的顺序，得到 $[(4, 3, 2), (2, 3, 5), (4, 1, 2)]$。注意，$[(1, 4, 2), (4, 2, 2), (3, 3, 5)]$ 不是 $q$ 的合法重排，因为 Bob 不能把属于不同三元组的数字交换。 作为 Alice 的朋友，你很清楚 Alice 只是在炫耀，所以你决定帮她一把，给出任意一个与给定数组 $q$ 一致的排列 $p$。

第一行包含一个整数 $n$（$5 \le n \le 10^5$），表示排列 $p$ 的长度。 接下来的 $n-2$ 行，每行包含 $3$ 个整数 $q_{i, 1}$、$q_{i, 2}$、$q_{i, 3}$（$1 \le q_{i, j} \le n$），表示经过打乱后的第 $i$ 个三元组的元素。注意，每个三元组内部的数字顺序和三元组之间的顺序都可能被打乱。 保证至少存在一个排列 $p$ 与输入一致。

输出 $n$ 个两两不同的整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$），使得排列 $p$ 与数组 $q$ 一致。 如果有多种答案，输出任意一种即可。

由 ChatGPT 4.1 翻译