Permutation Tree

AtCoder

IDarc095_d

Time2000ms

Memory256MB

Difficulty—

Takahashi has an ability to generate a tree using a permutation $(p_1,p_2,...,p_n)$ of $(1,2,...,n)$, in the following process: First, prepare Vertex $1$, Vertex $2$, ..., Vertex $N$. For each $i=1,2,...,n$, perform the following operation: * If $p_i = 1$, do nothing. * If $p_i \neq 1$, let $j'$ be the largest $j$ such that $p_j < p_i$. Span an edge between Vertex $i$ and Vertex $j'$. Takahashi is trying to make his favorite tree with this ability. His favorite tree has $n$ vertices from Vertex $1$ through Vertex $n$, and its $i$\-th edge connects Vertex $v_i$ and $w_i$. Determine if he can make a tree isomorphic to his favorite tree by using a proper permutation. If he can do so, find the lexicographically smallest such permutation. ## Constraints * $2 \leq n \leq 10^5$ * $1 \leq v_i, w_i \leq n$ * The given graph is a tree. ## Input Input is given from Standard Input in the following format: $n$ $v_1$ $w_1$ $v_2$ $w_2$ $:$ $v_{n-1}$ $w_{n-1}$ [samples] ## Notes For the definition of isomorphism of trees, see [wikipedia](https://en.wikipedia.org/wiki/Graph_isomorphism). Intuitively, two trees are isomorphic when they are the "same" if we disregard the indices of their vertices.

Samples

Input #1

Output #1

1 2 4 5 3 6

If the permutation $(1, 2, 4, 5, 3, 6)$ is used to generate a tree, it looks as follows:
![image](https://img.atcoder.jp/arc095/db000b879402aed649a1516620eb1e21.png)
This is isomorphic to the given graph.

Input #2

Output #2

1 2 3 4 5 6

Input #3

Output #3

\-1

API Response (JSON)

{
  "problem": {
    "name": "Permutation Tree",
    "description": {
      "content": "Takahashi has an ability to generate a tree using a permutation $(p_1,p_2,...,p_n)$ of $(1,2,...,n)$, in the following process: First, prepare Vertex $1$, Vertex $2$, ..., Vertex $N$. For each $i=1,2,",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc095_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Takahashi has an ability to generate a tree using a permutation $(p_1,p_2,...,p_n)$ of $(1,2,...,n)$, in the following process:\nFirst, prepare Vertex $1$, Vertex $2$, ..., Vertex $N$. For each $i=1,2,...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments