#include <bits/stdc++.h>
using namespace std;
const int MAX_N=1e5+10;

int n; bool ok=true;
vector<int> G[MAX_N];
int sub[MAX_N],dp[MAX_N];
vector<int> sz;

void dfs1(int v,int p){
    sub[v]=1;
    int big=0;
    for (int u:G[v]){
        if (u==p) continue;
        dfs1(u,v); sub[v]+=sub[u];
        if (sub[u]>=2) ++big;
    }
    if (n-sub[v]>=2) ++big;
    if (big>=3) ok=false;
}

void dfs2(int v,int p,int &s){
    if (p<0) dp[v]=0;
    if (dp[s]<dp[v]) s=v;
    for (int u:G[v]){
        if (u==p) continue;
        dp[u]=dp[v]+1;
        dfs2(u,v,s);
    }
}

void dfs3(int v,int p){
    int cnt=1; bool check=false;
    for (int u:G[v]){
        if (u==p) continue;
        if (sub[u]>=2) check=true;
    }
    for (int u:G[v]){
        if (u==p) continue;
        if (sub[u]>=2||!check) dfs3(u,v),check=true;
        else ++cnt;
    }
    sz.emplace_back(cnt);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i=0;i<n-1;++i){
        int u,v; cin >> u >> v; --u,--v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    dfs1(0,-1);
    if (!ok){cout << -1 << '\n'; return 0;}
    vector<int> v(2,0);
    dfs2(v[0],-1,v[0]);
    v[1]=v[0];
    dfs2(v[1],-1,v[1]);
    vector<int> ans;
    for (int i=0;i<2;++i){
        sz.clear();
        dfs1(v[i],-1); dfs3(v[i],-1);
        reverse(sz.begin(),sz.end());
        vector<int> res;
        int now=1;
        for (int x:sz){
            for (int j=0;j<x-1;++j) res.emplace_back(now+1+j);
            res.emplace_back(now);
            now+=x;
        }
        if (!i) ans=res;
        if (i&&res<ans) ans=res;
    }
    for (int i=0;i<n;++i) cout << ans[i] << (i+1==n?'\n':' ');
}
### Prompt

Your challenge is to write 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;
const int MAX_N=1e5+10;

int n; bool ok=true;
vector<int> G[MAX_N];
int sub[MAX_N],dp[MAX_N];
vector<int> sz;

void dfs1(int v,int p){
    sub[v]=1;
    int big=0;
    for (int u:G[v]){
        if (u==p) continue;
        dfs1(u,v); sub[v]+=sub[u];
        if (sub[u]>=2) ++big;
    }
    if (n-sub[v]>=2) ++big;
    if (big>=3) ok=false;
}

void dfs2(int v,int p,int &s){
    if (p<0) dp[v]=0;
    if (dp[s]<dp[v]) s=v;
    for (int u:G[v]){
        if (u==p) continue;
        dp[u]=dp[v]+1;
        dfs2(u,v,s);
    }
}

void dfs3(int v,int p){
    int cnt=1; bool check=false;
    for (int u:G[v]){
        if (u==p) continue;
        if (sub[u]>=2) check=true;
    }
    for (int u:G[v]){
        if (u==p) continue;
        if (sub[u]>=2||!check) dfs3(u,v),check=true;
        else ++cnt;
    }
    sz.emplace_back(cnt);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i=0;i<n-1;++i){
        int u,v; cin >> u >> v; --u,--v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    dfs1(0,-1);
    if (!ok){cout << -1 << '\n'; return 0;}
    vector<int> v(2,0);
    dfs2(v[0],-1,v[0]);
    v[1]=v[0];
    dfs2(v[1],-1,v[1]);
    vector<int> ans;
    for (int i=0;i<2;++i){
        sz.clear();
        dfs1(v[i],-1); dfs3(v[i],-1);
        reverse(sz.begin(),sz.end());
        vector<int> res;
        int now=1;
        for (int x:sz){
            for (int j=0;j<x-1;++j) res.emplace_back(now+1+j);
            res.emplace_back(now);
            now+=x;
        }
        if (!i) ans=res;
        if (i&&res<ans) ans=res;
    }
    for (int i=0;i<n;++i) cout << ans[i] << (i+1==n?'\n':' ');
}
```