Description

For a permutation $p$ of $1 \sim n$, define $G_p$ as an undirected graph constructed by the following method:

• For each $i \in (1,n]$, find the largest $j \in [1,i)$ such that $p_i > p_j$, and then add an edge between $i$ and $j$. If no such $j$ exists, do not add an edge.

You are given a tree $T$ with $n$ nodes.

Call $p$ a good permutation if and only if $G_p$ is isomorphic to $T$.

If a good permutation exists, output the lexicographically largest one. Otherwise, output $-1$.

Two undirected graphs $G_1, G_2$ are isomorphic if and only if there exists a permutation $q$ of $1 \sim n$ such that $\forall (u,v)\in G_1,(q_u,q_v)\in G_2,\forall (u,v)\notin G_1,(q_u,q_v)\notin G_2$.

Input Format

The first line contains an integer $n$.

The next $n-1$ lines each contain two integers $u,v$, indicating that there is an edge between $u$ and $v$.

Output Format

Output one line with $n$ integers representing the answer, or output a single number $-1$ indicating that there is no solution.

5
1 2
1 3
2 4
2 5

1 5 4 2 3

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

1 9 2 6 7 8 3 4 5

Hint

For $100\%$ of the data, $1\le u,v\le n\le 5\times 10^3$.

Note: the node labels in the sample explanations are the indices in $p$.

Sample Explanation 1

The shape of $G_p$ is as follows:

It can be proven that there is no better solution.

Sample Explanation 2

The shape of $G_p$ is as follows:

It can be proven that there is no better solution.

Translated by ChatGPT 5