← 返回题目列表

Codeforces · 36/E

E. 两条路径

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

有一次考古学家发现了m张神秘的纸,每张纸上都写着一对整数。众所周知,古人喜欢写下他们所走过的道路的索引,如“a b”或“b a”,其中a、b是道路连接的两个不同城市的索引。众所周知,这些神秘的文件是两本旅行日记的页面(当时,每一次新的旅程都会写一本新的日记)。

在一次旅程中,旅行者可以沿着同一条道路向一个或多个方向行走数次,但在这种情况下,他每次都会在日记中写下一个新条目。此外,考古学家认为,旅行者走在路上的方向对入口没有影响:看起来像“a b”的入口既可以指从a到b的道路,也可以指从b到a的道路。

考古学家想要将页面按正确的顺序排列并重建两条旅行路径,但不幸的是,他们不擅长编程。这就是你的用武之地。去帮助他们吧!

输入

第一个输入行包含整数 m (1 ≤ m ≤ 10000)。以下 m 行中的每一行描述一篇论文。每个描述由两个整数a、b(1 ≤ a,b ≤ 10000,a ≠ b)组成。

输出

在第一行输出数字L1。这是第一条路径的长度,即其描述中的论文数量。在下面的行中输出 L1 空格分隔的数字 - 描述第一条路径的论文的索引。在第三行和第四行中,类似地输出第二路径L2的长度和路径本身。两条路径必须至少包含一条道路,即必须满足条件 L1 > 0 且 L2 > 0。论文根据其在输入文件中出现的顺序从 1 到 m 进行编号。数字应按照旅行者通过相应道路的顺序输出。如果答案不唯一,则输出任意一个。

如果无法找到这两条路径,则输出“-1”。

不要忘记每张纸只能使用一次,即 L1 + L2 = m。

示例

输入 #1

2
4 5
4 3

输出 #1

1
2
1
1

输入 #2

1
1 2

输出 #2

-1