有一次考古学家发现了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