#include <bits/stdc++.h>
#define N 100100
using namespace std;

int n, ind[N], ld[N], cnt, num[N];
vector<int> G[N];

void dfs(int u, int p, int now, int &dep, int &pnt) {
    if (now > dep) dep = now, pnt = u;
    for (int v : G[u])
        if (v != p) dfs(v, u, now + 1, dep, pnt);
}

inline void getans(int *p) {
    int now = 1;
    for (int i = 1; i <= cnt; ++i, ++now) {
        int nxt = now + num[i];
        p[nxt] = now;
        for (int j = now; j < nxt; ++j)
            p[j] = ++now;
    }
}

int stk[N], top;

void dfs2(int u, int p, int d) {
    stk[++top] = u;
    if (u == d) {
        for (int i = top; i; --i)
            ind[stk[i]] = 1;
        memcpy(ld, stk, sizeof(stk));
        cnt = top;
    }
    for (int v : G[u])
        if (v != p) dfs2(v, u, d);
    stk[top--] = 0;
}

inline bool small(int *pa, int *pb) {
    for (int i = 1; i <= n; ++i)
        if (pa[i] != pb[i]) return pa[i] < pb[i];
    return false;
}

inline void write(int *p) {
    for (int i = 1; i <= n; ++i)
        printf("%d%c", p[i], " \n"[i == n]);
}

int pa[N], pb[N];

int main() {
#ifdef isLOCAL
    freopen("work.in", "r", stdin);
    freopen("work.out", "w", stdout);
#endif

    cin >> n;

    for (int i = 1, u, v; i < n; ++i)
        scanf("%d%d", &u, &v),
        G[u].push_back(v),
        G[v].push_back(u);

    int p1, p2, d;
    d = 0, dfs(1, 0, 0, d, p1);
    d = 0, dfs(p1, 0, 0, d, p2);

    dfs2(p1, 0, p2);

    for (int i = 1, u; i <= cnt; ++i) {
        u = ld[i];
        for (int v : G[u])
            if (!ind[v]) ++num[i], ind[v] = -1;
    }

    for (int i = 1; i <= n; ++i)
        if (!ind[i]) puts("-1"), exit(0);

    getans(pa);
    reverse(num + 1, num + cnt + 1);
    getans(pb);

    write(small(pa, pb) ? pa : pb);

    return 0;
}

### Prompt

Please create a solution in cpp 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>
#define N 100100
using namespace std;

int n, ind[N], ld[N], cnt, num[N];
vector<int> G[N];

void dfs(int u, int p, int now, int &dep, int &pnt) {
    if (now > dep) dep = now, pnt = u;
    for (int v : G[u])
        if (v != p) dfs(v, u, now + 1, dep, pnt);
}

inline void getans(int *p) {
    int now = 1;
    for (int i = 1; i <= cnt; ++i, ++now) {
        int nxt = now + num[i];
        p[nxt] = now;
        for (int j = now; j < nxt; ++j)
            p[j] = ++now;
    }
}

int stk[N], top;

void dfs2(int u, int p, int d) {
    stk[++top] = u;
    if (u == d) {
        for (int i = top; i; --i)
            ind[stk[i]] = 1;
        memcpy(ld, stk, sizeof(stk));
        cnt = top;
    }
    for (int v : G[u])
        if (v != p) dfs2(v, u, d);
    stk[top--] = 0;
}

inline bool small(int *pa, int *pb) {
    for (int i = 1; i <= n; ++i)
        if (pa[i] != pb[i]) return pa[i] < pb[i];
    return false;
}

inline void write(int *p) {
    for (int i = 1; i <= n; ++i)
        printf("%d%c", p[i], " \n"[i == n]);
}

int pa[N], pb[N];

int main() {
#ifdef isLOCAL
    freopen("work.in", "r", stdin);
    freopen("work.out", "w", stdout);
#endif

    cin >> n;

    for (int i = 1, u, v; i < n; ++i)
        scanf("%d%d", &u, &v),
        G[u].push_back(v),
        G[v].push_back(u);

    int p1, p2, d;
    d = 0, dfs(1, 0, 0, d, p1);
    d = 0, dfs(p1, 0, 0, d, p2);

    dfs2(p1, 0, p2);

    for (int i = 1, u; i <= cnt; ++i) {
        u = ld[i];
        for (int v : G[u])
            if (!ind[v]) ++num[i], ind[v] = -1;
    }

    for (int i = 1; i <= n; ++i)
        if (!ind[i]) puts("-1"), exit(0);

    getans(pa);
    reverse(num + 1, num + cnt + 1);
    getans(pb);

    write(small(pa, pb) ? pa : pb);

    return 0;
}

```