Description

Farmer John has many fences to repair each year. He always rides his horse along each fence and fixes the damaged parts.

John is as lazy as any other farmer. He dislikes riding horses, so he never passes through the same fence twice. You must write a program that reads the description of the fence network and calculates a path for repairing the fences such that each fence is traversed exactly once.

John can start riding from any vertex (i.e., the intersection point of two fences) and end at any vertex. Each fence connects two vertices, which are labeled from 1 to 500 (though some farms may not have all 500 vertices). A vertex can be connected to any number (≥1) of fences. All fences are connected (meaning you can reach any other fence from any starting fence).

Your program must output the riding path (represented by the sequence of vertex numbers traversed). If there are multiple possible solutions, the output should be the one that, when interpreted as a 500-base number, is the smallest (i.e., the solution with the smallest first number; if there are still multiple solutions, choose the one with the smallest second number, and so on). The input data guarantees at least one valid solution.

Input Format

Line 1: An integer F (1 ≤ F ≤ 1024), representing the number of fences;
Lines 2 to F+1: Each line contains two integers i, j (1 ≤ i, j ≤ 500), indicating that the fence connects vertices i and j.

Output Format

The output should consist of F+1 lines, each containing an integer, representing the sequence of vertex numbers traversed in the path.
Note that there may be multiple valid solutions, but only the one specified in the problem description will be considered correct.

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