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
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define N 100010
ll n;
vector<ll> g[N];
class Dist{
  public:
  ll d[N];
  void dfs(ll x,ll from,ll dep){
    d[x]=dep;
    for(auto y:g[x])if(y!=from){
      dfs(y,x,dep+1);
    }
  }
  ll main(ll s){
    dfs(s,0,0);
    ll ma=0,pnt=0;
    for(int i=1;i<=n;i++){
      if(d[i]>ma)ma=d[i],pnt=i;
    }
    return pnt;
  }
};
vector<ll> path;
bool dfs(ll x,ll from,ll p){
  path.push_back(x);
  if(x==p)return 1;
  for(auto y:g[x])if(y!=from){
    if(dfs(y,x,p))return 1;
  }
  path.pop_back();
  return 0;
}

ll ans[N];
void solve(){
    ans[1]=1; ll t=1;
    for(int i=1;i<path.size()-1;i++){
      ll k=g[path[i]].size()-2;
      ans[t+k+1]=t+1;
      for(int j=1;j<=k;j++)ans[t+j]=t+1+j;
      t+=k+1;
    }
    ans[n]=n;
}
ll res[N];
int main(){
    cin>>n;
    for(int i=0;i<n-1;i++){
      ll a,b;cin>>a>>b;
      g[a].push_back(b);
      g[b].push_back(a);
    }
    Dist A,B;
    ll a=A.main(1);
    ll b=B.main(a);
    dfs(a,0,b);
    ll sum=path.size();
    for(int i=1;i<path.size()-1;i++){
      sum+=g[path[i]].size()-2;
    }
    
    if(sum!=n){
      cout<<-1<<endl;
      return 0;
    }
    solve(); for(int i=1;i<=n;i++)res[i]=ans[i];
    reverse(path.begin(),path.end());
    solve();
    //for(int i=1;i<=n;i++)cout<<res[i]<<" ";cout<<endl;
    //for(int i=1;i<=n;i++)cout<<ans[i]<<" ";cout<<endl;
    bool smaller=0;
    for(int i=1;i<=n;i++){
      if(res[i]<ans[i]){smaller=1;break;}
      if(res[i]>ans[i])break;
    }
    if(smaller)for(int i=1;i<=n;i++)ans[i]=res[i];
    for(int i=1;i<=n;i++){
      if(i>1)cout<<" ";
      cout<<ans[i];
    }cout<<endl;
    return 0;
}

