#include <algorithm>
#include <cstdio>
#include <cstring>

const int N = 100050;

int n, pre[N], to[N * 2], nxt[N * 2], cnt;

inline void addEdge(int x, int y) {
  nxt[cnt] = pre[x];
  to[pre[x] = cnt++] = y;
  nxt[cnt] = pre[y];
  to[pre[y] = cnt++] = x;
}

void dfs(int x, int fa, int dx, int &y, int &d) {
  if (dx > d) {
    d = dx;
    y = x;
  }
  for (int i = pre[x]; i != -1; i = nxt[i])
    if (to[i] != fa)
      dfs(to[i], x, dx + 1, y, d);
}

int s[N], m;
int A[N], B[N];

bool dfs2(int x, int fa) {
  int &t = s[m++] = 0;
  int k = 0;
  for (int i = pre[x]; i != -1; i = nxt[i]) {
    int u = to[i];
    if (u == fa) ;
    else if (nxt[pre[u]] == -1) ++t;
    else if ((++k) > 1) return false;
    else if (!dfs2(to[i], x)) return false;
  }
  return true;
}

int main() {
  scanf("%d", &n);
  memset(pre, -1, sizeof pre);
  for (int i = 1, x, y; i < n; ++i) {
    scanf("%d%d", &x, &y);
    addEdge(x, y);
  }
  int x, d;
  dfs(1, 0, 0, x, d = 0);
  if (!dfs2(x, 0)) {
    puts("-1");
    return 0;
  }
  --s[m - 1];
  s[m++] = 0;
  for (int i = 0, j = 0; i < m; ++i) {
    A[j + s[i]] = j;
    for (int k = 0; k < s[i]; ++k, ++j) A[j] = j + 1;
    ++j;
  }
  for (int i = m - 1, j = 0; i >= 0; --i) {
    B[j + s[i]] = j;
    for (int k = 0; k < s[i]; ++k, ++j) B[j] = j + 1;
    ++j;
  }
  bool ok = false;
  for (int i = 0; i < n; ++i)
    if (A[i] != B[i]) {
      ok = A[i] > B[i];
      break;
    }
  for (int i = 0; i < n; ++i)
    printf("%d ", (ok ? B : A)[i] + 1);
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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}


Output

If there is no permutation that can generate a tree isomorphic to Takahashi's favorite tree, print `-1`. If it exists, print the lexicographically smallest such permutation, with spaces in between.

Examples

Input

6
1 2
1 3
1 4
1 5
5 6


Output

1 2 4 5 3 6


Input

6
1 2
2 3
3 4
1 5
5 6


Output

1 2 3 4 5 6


Input

15
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15


Output

-1

### Response

```cpp
#include <algorithm>
#include <cstdio>
#include <cstring>

const int N = 100050;

int n, pre[N], to[N * 2], nxt[N * 2], cnt;

inline void addEdge(int x, int y) {
  nxt[cnt] = pre[x];
  to[pre[x] = cnt++] = y;
  nxt[cnt] = pre[y];
  to[pre[y] = cnt++] = x;
}

void dfs(int x, int fa, int dx, int &y, int &d) {
  if (dx > d) {
    d = dx;
    y = x;
  }
  for (int i = pre[x]; i != -1; i = nxt[i])
    if (to[i] != fa)
      dfs(to[i], x, dx + 1, y, d);
}

int s[N], m;
int A[N], B[N];

bool dfs2(int x, int fa) {
  int &t = s[m++] = 0;
  int k = 0;
  for (int i = pre[x]; i != -1; i = nxt[i]) {
    int u = to[i];
    if (u == fa) ;
    else if (nxt[pre[u]] == -1) ++t;
    else if ((++k) > 1) return false;
    else if (!dfs2(to[i], x)) return false;
  }
  return true;
}

int main() {
  scanf("%d", &n);
  memset(pre, -1, sizeof pre);
  for (int i = 1, x, y; i < n; ++i) {
    scanf("%d%d", &x, &y);
    addEdge(x, y);
  }
  int x, d;
  dfs(1, 0, 0, x, d = 0);
  if (!dfs2(x, 0)) {
    puts("-1");
    return 0;
  }
  --s[m - 1];
  s[m++] = 0;
  for (int i = 0, j = 0; i < m; ++i) {
    A[j + s[i]] = j;
    for (int k = 0; k < s[i]; ++k, ++j) A[j] = j + 1;
    ++j;
  }
  for (int i = m - 1, j = 0; i >= 0; --i) {
    B[j + s[i]] = j;
    for (int k = 0; k < s[i]; ++k, ++j) B[j] = j + 1;
    ++j;
  }
  bool ok = false;
  for (int i = 0; i < n; ++i)
    if (A[i] != B[i]) {
      ok = A[i] > B[i];
      break;
    }
  for (int i = 0; i < n; ++i)
    printf("%d ", (ok ? B : A)[i] + 1);
  return 0;
}

```