Problem Statement

You are given an undirected connected graph with ~n~ vertices and ~n - 1~ edges. Output the Euler Tour order of this graph of the graph starting at node ~1~. If you have a choice to visit more than one child, visit the child with the lowest value/label.

You only need to record the first and last visits to a node in your Euler Tour.

Input Format

Your first line will contain a single integer ~n~. Your next ~n - 1~ lines will contain two space-separated integers each ~u~ and ~v~ representing an edge from ~u~ to ~v~.

Output Format

You should output ordering of the vertices along an Euler tour of the graph starting at node ~1~.

Constraints

• ~1 \leq n \leq 10^5~
• ~1 \leq u, v \leq n~ and ~u \neq v~

Template

import sys
sys.setrecursionlimit(int(1e9))

n = int(input())
edges = [map(int, input().split()) for _ in range(n - 1)]

# print your output

Sample Cases

Input 1

8
1 2
2 3
2 4
1 5
5 6
6 7
6 8

Output 1

1 2 3 3 4 4 2 5 6 7 7 8 8 6 5 1

Input 2

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

Output 2

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