P7920 [Kubic] Permutation

It is recommended to read the background of Problem E first.

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$.

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 one line with $n$ integers representing the answer, or output a single number $-1$ indicating that there is no solution.

For $100\%$ of the data, $1\le u,v\le n\le 5\times 10^3$. ||Score|$n$|Special Property| |:-:|:-:|:-:|:-:| |$\operatorname{Subtask}1$|$15$|$\le 8$|None| |$\operatorname{Subtask}2$|$5$|No special limit|The tree degenerates into a chain| |$\operatorname{Subtask}3$|$15$|No special limit|The number of nodes with degree $\ge 3$ is $\le 1$| |$\operatorname{Subtask}4$|$20$|$\le 100$|None| |$\operatorname{Subtask}5$|$20$|$\le 10^3$|None| |$\operatorname{Subtask}6$|$25$|No special limit|None| **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