← 返回题目列表

Codeforces · 490/B

B. 队列

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

午休期间,所有伯兰州立大学的学生都在美食广场排队。然而,原来美食广场也午休了,暂时停止营业了。

站在无人服务的队列里真是太无聊了!于是,每个学生都记下了自己前面排队的学生和自己后面排队的学生的学号。如果没有人站在学生的前面或后面(即他是第一个或最后一个),则他写下数字 0(在伯兰州立大学,学生 ID 从 1 开始编号)。

之后,所有的学生都各忙各的。当他们回来时,他们发现恢复队列并不是一件容易的事。

通过队列中邻居的学号号码帮助学生恢复队列状态。

输入

第一行包含整数 n (2 ≤ n ≤ 2·105) — 队列中的学生数量。

接下来是 n 行,第 i 行包含一对整数 ai,bi (0 ≤ ai, bi ≤ 106),其中 ai 是学生前面的人的 ID 号,bi 是学生后面的人的 ID 号。这些行以任意顺序给出。如果邻居不存在,则给出值 0,而不是邻居的 ID 号。

所有学生的身份证号码都是不同的。保证记录也与所有学生按某种顺序站立的队列相对应。

输出

打印一个由 n 个整数组成的序列 x1, x2, ..., xn — 所有学生的 ID 号序列,按照队列中从第一个学生到最后一个学生的顺序排列。

示例

输入 #1

4
92 31
0 7
31 0
7 141

输出 #1

92 7 31 141

注意

该图展示了第一个样本的队列。