Lexicographically Maximum Good Permutation

Let \(p = [p_1,p_2,\dots,p_n]\) be a permutation of \(\{1,2,\dots,n\}\). We define an undirected graph \(G_p\) on \(n\) vertices (indexed \(1\) through \(n\)) as follows: for every index \(i\) with \(2\le i\le n\), let \(j\) be the largest index in \([1,i)\) such that \(p_i > p_j\) (note that because \(p_1=1\) must hold for connectivity, such a \(j\) always exists). Then add an edge between vertices \(i\) and \(j\).

We are also given a tree \(T\) on \(n\) vertices. We call \(p\) a good permutation if \(G_p\) is isomorphic to \(T\); that is, there exists a relabeling \(q\) (a permutation on \(\{1,\dots,n\}\)) such that for every pair \((u,v)\):

[ (u,v)\in E(G_p) \Longleftrightarrow (q_u,q_v)\in E(T). ]

If there exists at least one good permutation, output the lexicographically maximum one (as an array of \(n\) numbers). Otherwise, output -1.

Important observations:

• For \(G_p\) to be connected (i.e. a tree) every index \(i\ge2\) must have at least one \(j\) with \(p_j < p_i\). In particular, the minimum element must appear at the beginning so that \(p_1=1\).
• The construction rule guarantees that for each \(i\ge2\) if we denote \(f(i)=\max\{j\,|\,1\le j<i \text{ and } p_j<p_i\}\) then the edge \((i,f(i))\) is added and moreover for every index \(k\) with \(f(i)<k p_i\) (otherwise the candidate would be chosen later than \(f(i)\)).
• Since the definition of graph isomorphism permits an arbitrary renumbering of vertices, the given tree \(T\) may be “re‐labelled” so that it exactly matches the structure of \(G_p\) produced by an appropriate permutation \(p\) starting with \(1\).

Input Format

The first line contains a single integer \(n\) (the number of vertices). Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) (\(1 \le u,v \le n\)) indicating an edge in the tree \(T\).

Output Format

If a good permutation exists, output the lexicographically maximum good permutation (\(n\) space‐separated integers) in one line. Otherwise, output -1.

Note on Lexicographical Maximum: A permutation \(a\) is lexicographically larger than permutation \(b\) if at the first position where they differ, the element in \(a\) is larger than the corresponding element in \(b\).

inputFormat

The first line contains an integer \(n\) \((2\le n\le N)\). Each of the next \(n-1\) lines contains two integers \(u\) and \(v\), denoting an edge in the tree \(T\).

outputFormat

If a good permutation exists, output the lexicographically maximum good permutation as \(n\) space‐separated integers. Otherwise, output -1.

sample

3
1 2
1 3

1 3 2