题目描述

Farmer John 每年都要骑马经过农场里的每一段栅栏并修复破损处。他不愿重复经过同一段栅栏。

农场有 $m$ 段栅栏，每段连接两个编号在 $1$ 到 $500$ 之间的顶点。一个顶点可以连接任意多段栅栏，两个顶点之间也可能有多段栅栏。所有栅栏属于同一连通部分。

请输出一条经过每段栅栏恰好一次的路线。输入保证至少存在一条可行路线。若有多条路线，比较依次经过的顶点序列，输出字典序最小的一条。

输入格式

第一行输入整数 $m$。接下来 $m$ 行，每行两个整数 $u,v$，表示一段连接两个顶点的栅栏。

输出格式

输出 $m+1$ 行，每行一个整数，按顺序表示路线经过的顶点编号。

数据范围与约定

$1\le m\le1024$，$1\le u,v\le500$。

可见测试数据

输入数据 1

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

输出数据 1

1
2
3
4
5
6
1

输入数据 2

1
1 2

输出数据 2

1
2

输入数据 3

4
4 1
3 4
2 3
1 2

输出数据 3

1
2
3
4
1