P14733 [ICPC 2022 Seoul R] Two Choreographies

Somim 和 Eunjoo 是著名的舞者和非常有才华的编舞家，但他们最近没有赢得比赛。为了今年赢得比赛，他们正试图互相帮助创作新的编舞。实际上，还没有人尝试过流畅地衔接静态动作，而他们将首次尝试！ Somim 和 Eunjoo 想为各自创作一套包含 $n$ 个静态动作的编舞。他们非常了解如何流畅地衔接静态动作，并得出结论：恰好 $2n - 3$ 个无序静态动作对足以让他们自由表演。动作对 $\{A, B\}$ 的顺序无关紧要，即如果动作 $B$ 可以在动作 $A$ 之后衔接，那么 $A$ 也可以在 $B$ 之后衔接。 Somim 和 Eunjoo 想要表演的编舞如下：两套编舞持续时间相同，这意味着每套编舞应包含相同数量的静态动作。每套编舞应以其第一个静态动作结束。更准确地说，两套编舞 $C_1$ 和 $C_2$ 是由 $l$ 个不同的静态动作组成的序列，$C_1 = (a_0, a_1, ..., a_l)$ 且 $C_2 = (b_0, b_1, ..., b_l)$，其中 $a_0 = a_l$ 且 $b_0 = b_l$。为了让观众感到有趣，$C_1$ 和 $C_2$ 应该不同，即存在某个 $0 \leq i \leq l - 1$，使得 $C_1$ 中的 $\{a_i, a_{i+1}\}$ 不等于 $C_2$ 中任何 $0 \leq j \leq l - 1$ 对应的 $\{b_j, b_{j+1}\}$。（例如，$(1,2,3,4,5,1)$ 和 $(3,4,5,2,1,3)$ 是不同的，但 $(1,2,3,4,5,1)$ 和 $(3,4,5,1,2,3)$ 是相同的。）此外，观众容易感到无聊，所以编舞不能太短，必须包含至少 $3$ 个不同的静态动作，即 $l \geq 3$。 为此，给定 $2n - 3$ 个无序动作对 $P$，这些动作对来自 $n$ 个不同的静态动作 $m_1, ..., m_n$，两位舞者可以表演。对于一对 $\{m_i, m_j\}$（$i \neq j$），$m_i$ 和 $m_j$ 中的一个可以在序列中出现在另一个之后；它们之间没有特定的顺序。你需要编写一个程序，找出两套不同的编舞 $C_1 = (a_0, a_1, ..., a_l)$ 和 $C_2 = (b_0, b_1, ..., b_l)$，长度相同且 $l \geq 3$，使得对于任意 $0 \leq i \leq l - 1$，有 $\{a_i, a_{i+1}\} \in P$，$\{b_i, b_{i+1}\} \in P$，且 $a_0 = a_l$，$b_0 = b_l$。

你的程序需要从标准输入读取数据。输入的第一行包含一个整数 $n$ ($4 \leq n \leq 100,000$)，其中 $n$ 是两位舞者可以表演的静态动作数量。每个静态动作被编号为 $1$ 到 $n$ 的整数。接下来的 $2n - 3$ 行表示 $2n - 3$ 个无序静态动作对 $P$。每行包含两个不同的整数，表示 $P$ 中的一个动作对。注意，$P$ 中没有两个对是相同的。

你的程序需要向标准输出写入数据。如果你找不到两套静态动作编舞，则输出 $-1$。否则，你应该恰好输出三行。第一行包含一个整数 $l \geq 3$，表示每套编舞中不同静态动作的数量。第二行包含恰好 $l$ 个整数，用空格分隔，按顺序表示一套编舞的 $l$ 个静态动作。最后一个重复的动作应省略。第三行包含恰好 $l$ 个整数，表示另一套编舞。

翻译由 DeepSeek V3 完成