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.

-----Notes-----
For the definition of isomorphism of trees, see wikipedia. Intuitively, two trees are isomorphic when they are the "same" if we disregard the indices of their vertices.

-----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.

-----Sample Input-----
6
1 2
1 3
1 4
1 5
5 6

-----Sample Output-----
1 2 4 5 3 6

If the permutation (1, 2, 4, 5, 3, 6) is used to generate a tree, it looks as follows:

This is isomorphic to the given graph.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import sys\n\ninput=sys.stdin.readline\nsys.setrecursionlimit(2*10**5)\n\nn=int(input())\nedge=[[] for i in range(n)]\nfor i in range(n-1):\n    v,w=map(int,input().split())\n    edge[v-1].append(w-1)\n    edge[w-1].append(v-1)\n\nif n==2:\n    print(1,2);return\n\nleafcnt=[0]*n\nfor v in range(n):\n    for nv in edge[v]:\n        if len(edge[nv])==1:\n            leafcnt[v]+=1\n\nused=[False]*n\nline=[]\ndef line_check(v):\n    used[v]=True\n    line.append(leafcnt[v])\n    flag=False\n    for nv in edge[v]:\n        if not used[nv] and len(edge[nv])!=1:\n            if not flag:\n                line_check(nv)\n                flag=True\n            else:\n                return False\n    return True\n\nfor v in range(n):\n    if not used[v] and len(edge[v])-leafcnt[v]<=1 and len(edge[v])!=1:\n        if not line:\n            check=line_check(v)\n            if not check:\n                print(-1);return()\n        else:\n            print(-1);return()\n\n\nline_rev=line[::-1]\nres=min(line,line_rev)\nres=[0]+res+[0]\nres[1]-=1\nres[-2]-=1\n\nans=[]\nL=1\nfor val in res:\n    R=L+val\n    for i in range(L+1,R+1):\n        ans.append(i)\n    ans.append(L)\n    L=R+1\n\nprint(*ans)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: