#include<bits/stdc++.h>
using namespace std;
using Int = long long;

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<vector<Int> > G(n);
  for(Int i=1;i<n;i++){
    Int x,y;
    cin>>x>>y;
    x--;y--;
    G[x].emplace_back(y);
    G[y].emplace_back(x);
  }
  Int x,y;
  {
    Int a=-1,b=-1;
    function<void(Int,Int,Int)> dfs=[&](Int v,Int p,Int d){
      //cout<<v<<" "<<p<<" "<<d<<endl;
      if(b<d) a=v,b=d;
      for(Int u:G[v])
	if(u!=p) dfs(u,v,d+1);
    };
    dfs(0,-1,0);
    x=a;a=-1;b=-1;
    dfs(x,-1,0);
    y=a;
  }
  //cout<<x<<" "<<y<<endl;

  vector<Int> ans(n,n);
  vector<Int> dp(n,-1);
  
  Int ok;
  function<void(Int,Int)> dfs=[&](Int v,Int p){
    if(p<0) ok=1;
    dp[v]=0;
    Int cnt=0;
    for(Int u:G[v]){
      if(u==p) continue;
      dfs(u,v);
      chmax(dp[v],dp[u]);
      if(dp[u]>1) cnt++;
    }
    ok&=cnt<=1;
    dp[v]++;
  };

  vector<Int> tmp;
  Int idx;
  function<void(Int,Int)> dfs2=[&](Int v,Int p){
    if(p<0) tmp.clear(),idx=0;
    Int nv=-1;
    Int cur=idx++,cnt=0;
    for(Int u:G[v]){
      if(u==p) continue;
      cnt++;
      if(nv<0||dp[u]!=1) nv=u; 
    }
    if(~nv) cnt--;
    for(Int i=0;i<cnt;i++) tmp.emplace_back(idx++);
    tmp.emplace_back(cur);
    if(~nv) dfs2(nv,v);
  };

  dfs(x,-1);
  if(ok) dfs2(x,-1);
  chmin(ans,tmp);
  
  dfs(y,-1);
  if(ok) dfs2(y,-1);
  chmin(ans,tmp);
  
  if(ans[0]==n) cout<<-1<<endl;
  else{
    for(Int i=0;i<n;i++){
      if(i) cout<<" ";
      cout<<ans[i]+1;
    }
    cout<<endl;
  }
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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;
using Int = long long;

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<vector<Int> > G(n);
  for(Int i=1;i<n;i++){
    Int x,y;
    cin>>x>>y;
    x--;y--;
    G[x].emplace_back(y);
    G[y].emplace_back(x);
  }
  Int x,y;
  {
    Int a=-1,b=-1;
    function<void(Int,Int,Int)> dfs=[&](Int v,Int p,Int d){
      //cout<<v<<" "<<p<<" "<<d<<endl;
      if(b<d) a=v,b=d;
      for(Int u:G[v])
	if(u!=p) dfs(u,v,d+1);
    };
    dfs(0,-1,0);
    x=a;a=-1;b=-1;
    dfs(x,-1,0);
    y=a;
  }
  //cout<<x<<" "<<y<<endl;

  vector<Int> ans(n,n);
  vector<Int> dp(n,-1);
  
  Int ok;
  function<void(Int,Int)> dfs=[&](Int v,Int p){
    if(p<0) ok=1;
    dp[v]=0;
    Int cnt=0;
    for(Int u:G[v]){
      if(u==p) continue;
      dfs(u,v);
      chmax(dp[v],dp[u]);
      if(dp[u]>1) cnt++;
    }
    ok&=cnt<=1;
    dp[v]++;
  };

  vector<Int> tmp;
  Int idx;
  function<void(Int,Int)> dfs2=[&](Int v,Int p){
    if(p<0) tmp.clear(),idx=0;
    Int nv=-1;
    Int cur=idx++,cnt=0;
    for(Int u:G[v]){
      if(u==p) continue;
      cnt++;
      if(nv<0||dp[u]!=1) nv=u; 
    }
    if(~nv) cnt--;
    for(Int i=0;i<cnt;i++) tmp.emplace_back(idx++);
    tmp.emplace_back(cur);
    if(~nv) dfs2(nv,v);
  };

  dfs(x,-1);
  if(ok) dfs2(x,-1);
  chmin(ans,tmp);
  
  dfs(y,-1);
  if(ok) dfs2(y,-1);
  chmin(ans,tmp);
  
  if(ans[0]==n) cout<<-1<<endl;
  else{
    for(Int i=0;i<n;i++){
      if(i) cout<<" ";
      cout<<ans[i]+1;
    }
    cout<<endl;
  }
  return 0;
}

```