Odd Path Permutation on a Tree

Given a tree with n nodes (numbered from 1 to n) and each edge of length 1, construct a permutation p of the nodes such that for every consecutive pair p_i and p_i+1 (for 1 ≤ i < n), the length of the simple path between them is odd. In other words, if we bipartition the tree into two sets (say, A and B) according to their parity distance from an arbitrary root, the condition is equivalent to: the two consecutive nodes must belong to different partitions.

If there exists a valid permutation, output the lexicographically smallest such permutation; otherwise, output -1.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of nodes in the tree. Each of the following n-1 lines contains two integers u and v (1 ≤ u, v ≤ n), representing an edge between nodes u and v.

outputFormat

If a valid permutation exists, output the lexicographically smallest permutation p (n space-separated integers). Otherwise, output -1.

sample

3
1 2
2 3

1 2 3