Polygon Vertex Restoration

HWX is famous for his love of geometry and the fact that he solves every problem. One day, while LXC was playing with Logo, he came up with a challenge. He drew an n‐sided polygon and labeled its vertices with consecutive natural numbers 1, 2, 3, …, n. To make things interesting, he also drew several non‐intersecting diagonals. Then he recorded every segment (both the polygon edges and the diagonals) on a piece of paper. For example, for the polygon shown below he wrote down: (1, 3), (3, 2), (2, 4), (4, 5), (5, 1), (1, 4) and (3, 4). But just as he was pleased with his work, his computer restarted automatically and he lost his Logo program. Now, using the information recorded on paper, can you help him restore the ordering of the vertex numbering along the polygon?

Note: The given segments come from a triangulation of a convex polygon. In such a triangulation, every diagonal (interior edge) is shared by exactly two triangles, whereas each boundary (polygon) edge is incident to only one triangle. Two vertices constitute a boundary edge if and only if the number of common neighbors (excluding the two vertices themselves) is exactly one. To restore the polygon, form the boundary graph from the detected boundary edges. This graph is a simple cycle containing all n vertices. Output the sequence of vertices in the order they appear along the boundary, starting from the smallest numbered vertex and then choosing the smaller adjacent vertex as the second vertex.

inputFormat

The input begins with a line containing a single integer n (n ≥ 3), the number of vertices of the polygon. It is followed by 2*n - 3 lines, each containing two integers u and v (1 ≤ u, v ≤ n, u ≠ v), representing a segment between vertex u and vertex v. These segments include all the sides of the polygon and some non-intersecting diagonals.

outputFormat

Output a single line containing n integers, representing the restored order of the polygon vertices along the boundary (in clockwise or counterclockwise order). The sequence must start with the smallest vertex number, and among its two boundary neighbors, choose the one with the smaller label as the second vertex.

sample

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

1 3 2 4 5