题目描述

给定一个连通的无向栅栏网络，请找出一条恰好经过每条栅栏一次的路线。可以在任意顶点开始和结束。

如果有多条可行路线，输出顶点编号序列字典序最小的那一条：先比较第一个编号，较小者优先；相同时继续比较下一个编号。保证至少有一条可行路线。

输入格式

第一行一个整数 $F$，表示栅栏数。接下来 $F$ 行，每行两个整数，表示一条栅栏的端点编号。

输出格式

输出 $F+1$ 行，每行一个顶点编号，依次表示所求路线。

样例

9
1 2
2 3
3 4
4 2
4 5
2 5
5 6
5 7
4 6

1
2
3
4
2
5
4
6
5
7

数据范围

$1\le F\le1024$。顶点编号在 $1$ 到 $500$ 之间，编号不一定连续。栅栏两端不同，允许多个栅栏连接同一对顶点。所有栅栏连通且存在欧拉路。