MianKing has a Graph Constructer : The input of it is a sequence and the output of it is an undirected graph with nodes, edge is in this graph if and only if

For example, if the input is , the output is the graph

Now GreenKing has a tree with nodes, MianKing wants to find a sequence as input to get this tree. You need to help him find a sequence satisfy the condition.

The first line has one integer .

Then there are  lines, each line has two integers  denotes an edge in the tree.

.

Output  integers  denotes the sequence you find.

You should guaranteed that 

It's guaranteed that the solution always exists.

3
1 2
2 3

1 1152921504606846974 1