Somin 和 Eunjoo 是著名的舞者，也是非常有天赋的编舞家，但他们最近在比赛中没有取得好成绩。为了在今年的比赛中获胜，他们正试图互相帮助，创作新的编舞。事实上，还没有人尝试过平滑地连接静态动作，而他们打算第一次尝试！

Somin 和 Eunjoo 希望为他们每个人制作两段包含 $n$ 个静态动作的编舞。他们非常了解如何平滑地连接静态动作，并得出结论：恰好 $2n - 3$ 个无序的静态动作对足以让他们自由表演。一对动作 $\{A, B\}$ 中静态动作的顺序并不重要，即如果动作 $B$ 可以接在动作 $A$ 之后，那么 $A$ 也可以接在 $B$ 之后。

Somin 和 Eunjoo 想要表演的编舞如下。这两段编舞持续的时间相同，这意味着每一段都应包含相同数量的静态动作。每段编舞都应以其第一个静态动作结束。更准确地说，两段编舞 $C_1$ 和 $C_2$ 是由 $l$ 个不同的静态动作组成的序列，$C_1 = (a_0, a_1, \dots, a_{l-1})$ 和 $C_2 = (b_0, b_1, \dots, b_{l-1})$，其中 $a_0 = a_l$ 且 $b_0 = b_l$。为了观众的娱乐性，$C_1$ 和 $C_2$ 必须不同，即存在某个 $0 \le i \le l-1$，使得 $C_1$ 中的 $\{a_i, a_{i+1}\}$ 不等于 $C_2$ 中 $0 \le j \le 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 \ge 3$。

为此，给定 $n$ 个不同的静态动作 $1, \dots, n$ 中两名舞者可以表演的 $2n - 3$ 个无序动作对 $P$。对于一对 $\{m_i, m_j\}$（其中 $i \neq j$），$m_i$ 和 $m_j$ 中的一个可以出现在序列中另一个的后面；它们之间没有特定的顺序。你需要编写一个程序来寻找两段不同的编舞 $C_1 = (a_0, a_1, \dots, a_{l-1})$ 和 $C_2 = (b_0, b_1, \dots, b_{l-1})$，它们具有相同的长度 $l \ge 3$，使得对于任何 $0 \le i \le 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 \le n \le 100,000$)，其中 $n$ 是两名舞者可以表现的静态动作数量。每个静态动作编号为 1 到 $n$ 的整数。接下来的 $2n - 3$ 行表示 $P$ 中的 $2n - 3$ 个无序动作对。每行包含两个不同的整数，表示 $P$ 中一对静态动作。注意，$P$ 中没有两个相同的动作对。

输出格式

程序将结果写入标准输出。如果无法找到两段编舞，则输出 -1。否则，应准确输出三行。第一行包含一个整数 $l \ge 3$，表示每段编舞中不同静态动作的数量。第二行包含 $l$ 个由空格分隔的整数，依次表示其中一段编舞的 $l$ 个静态动作。重复的最后一个动作应省略。第三行包含 $l$ 个整数，表示另一段编舞。

样例

样例输入 1

4
1 2
1 3
1 4
2 3
2 4

样例输出 1

3
1 2 3
1 2 4

样例输入 2

5
1 2
1 3
1 4
1 5
2 3
2 5
3 4

样例输出 2

3
1 2 3
1 3 4

样例输入 3

7
1 2
3 4
5 6
5 2
3 1
6 1
4 2
4 5
2 6
3 6
1 5

样例输出 3

4
6 1 5 2
4 2 1 3