有一天,鲍勃收到一封装在信封里的信。鲍勃知道,当 Berland 的邮政官员直接从城市“A”寄信到城市“B”时,他们会在上面盖上“A B”或“B A”的戳记。不幸的是,通常不可能将信件从发件人的城市直接发送到收件人的城市,这就是为什么信件要通过一些中间城市发送。邮局官员在发送信件时绝不会以该信件的路线多次包含某个城市的方式发送信件。鲍勃确信邮递员准确地在信件上盖章。
鲍勃的信的信封上有 n 张邮票。他明白,这封信可能的途径只有两种。但邮票数量众多,鲍勃无法确定自己的路线。这就是为什么他请求你帮助他。找出这封信可能的路径之一。
输入
第一行包含整数 n (1 ≤ n ≤ 105) — 信封上的邮票数量。接下来是 n 行,每行有两个整数——邮票的描述。每张邮票都描述了信件发送城市的索引。城市指数为1~109之间的整数。各个城市的指数各不相同。每次信件从一个城市寄往另一个城市时,信封上都会贴上一张邮票。保证给定的邮票对应于从某个城市到另一个城市的某些有效路线。
输出
输出 n + 1 个数字 — 信件的两条可能路线之一中的城市索引。
示例
输入 #1
2 1 100 100 2
输出 #1
2 100 1
输入 #2
3 3 1 100 2 3 2
输出 #2
100 2 3 1