#include <bits/stdc++.h>

using namespace std;

template< typename T >
struct edge {
  int src, to;
  T cost;

  edge(int to, T cost) : src(-1), to(to), cost(cost) {}

  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

template< typename T >
pair< T, int > dfs(const WeightedGraph< T > &g, int idx, int par) {
  pair< T, int > ret(0, idx);
  for(auto &e : g[idx]) {
    if(e.to == par) continue;
    auto cost = dfs(g, e.to, idx);
    cost.first += e.cost;
    ret = max(ret, cost);
  }
  return ret;
}

template< typename T >
pair< int, int > tree_diameter(const WeightedGraph< T > &g) {
  auto p = dfs(g, 0, -1);
  auto q = dfs(g, p.second, -1);
  return {p.second, q.second};
}

vector< int > vv;
int ptr;

void dfs2(WeightedGraph< int > &g, int s, int t, int par = -1) {
  int space = 0, link = -1;
  for(auto &to : g[s]) {
    if(to == par) continue;
    if(g[to].size() == 1 && to != t) ++space;
    else link = to;
  }
  for(int i = 0; i < space; i++) {
    vv[ptr + i] = ptr + i + 1;
  }
  ptr += space;
  vv[ptr] = ptr - space;
  ++ptr;
  if(~link) dfs2(g, link, t, s);
}

int main() {
  int N;
  cin >> N;
  WeightedGraph< int > g(N);
  for(int i = 1; i < N; i++) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    g[x].emplace_back(y, 1);
    g[y].emplace_back(x, 1);
  }
  auto pp = tree_diameter(g);
  vv.resize(N);
  ptr = 0;
  dfs2(g, pp.first, pp.second);
  if(ptr < N) {
    cout << -1 << endl;
    return 0;
  }
  auto latte = vv;
  ptr = 0;
  dfs2(g, pp.second, pp.first);
  auto malta = vv;
  if(latte > malta) swap(latte, malta);
  for(auto &p : latte) cout << p + 1 << " ";
  cout << endl;
}


### Prompt

Generate a cpp solution to the following problem:

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 <bits/stdc++.h>

using namespace std;

template< typename T >
struct edge {
  int src, to;
  T cost;

  edge(int to, T cost) : src(-1), to(to), cost(cost) {}

  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

template< typename T >
pair< T, int > dfs(const WeightedGraph< T > &g, int idx, int par) {
  pair< T, int > ret(0, idx);
  for(auto &e : g[idx]) {
    if(e.to == par) continue;
    auto cost = dfs(g, e.to, idx);
    cost.first += e.cost;
    ret = max(ret, cost);
  }
  return ret;
}

template< typename T >
pair< int, int > tree_diameter(const WeightedGraph< T > &g) {
  auto p = dfs(g, 0, -1);
  auto q = dfs(g, p.second, -1);
  return {p.second, q.second};
}

vector< int > vv;
int ptr;

void dfs2(WeightedGraph< int > &g, int s, int t, int par = -1) {
  int space = 0, link = -1;
  for(auto &to : g[s]) {
    if(to == par) continue;
    if(g[to].size() == 1 && to != t) ++space;
    else link = to;
  }
  for(int i = 0; i < space; i++) {
    vv[ptr + i] = ptr + i + 1;
  }
  ptr += space;
  vv[ptr] = ptr - space;
  ++ptr;
  if(~link) dfs2(g, link, t, s);
}

int main() {
  int N;
  cin >> N;
  WeightedGraph< int > g(N);
  for(int i = 1; i < N; i++) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    g[x].emplace_back(y, 1);
    g[y].emplace_back(x, 1);
  }
  auto pp = tree_diameter(g);
  vv.resize(N);
  ptr = 0;
  dfs2(g, pp.first, pp.second);
  if(ptr < N) {
    cout << -1 << endl;
    return 0;
  }
  auto latte = vv;
  ptr = 0;
  dfs2(g, pp.second, pp.first);
  auto malta = vv;
  if(latte > malta) swap(latte, malta);
  for(auto &p : latte) cout << p + 1 << " ";
  cout << endl;
}


```