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\n#sys.setrecursionlimit(10 ** 6)\nint1 = lambda x: int(x) - 1\np2D = lambda x: print(*x, sep="\\n")\ndef II(): return int(sys.stdin.readline())\ndef MI(): return map(int, sys.stdin.readline().split())\ndef MI1(): return map(int1, sys.stdin.readline().split())\ndef LI(): return list(map(int, sys.stdin.readline().split()))\ndef LLI(rows_number): return [LI() for _ in range(rows_number)]\ndef SI(): return sys.stdin.readline()[:-1]\n\nn=II()\nto=[[] for _ in range(n)]\nfor _ in range(n-1):\n    u,v=MI1()\n    to[u].append(v)\n    to[v].append(u)\n#print(to)\n\ndef far(u):\n    stack=[(u,-1,0)]\n    mxd=mxu=-1\n    while stack:\n        u,pu,d=stack.pop()\n        if d>mxd:\n            mxd=d\n            mxu=u\n        for v in to[u]:\n            if v==pu:continue\n            stack.append((v,u,d+1))\n    return mxu,mxd\n\ns,_=far(0)\nt,dist=far(s)\n#print(s,t,dist)\n\ndef makepath(u,t):\n    stack=[(u,-1)]\n    while stack:\n        u,pu=stack.pop()\n        while path and path[-1]!=pu:path.pop()\n        path.append(u)\n        if u==t:return\n        for v in to[u]:\n            if v==pu:continue\n            stack.append((v,u))\n\npath=[s]\nmakepath(s,t)\n#print(path)\n\nleg=[]\nfor u in path[1:-1]:leg.append(len(to[u])-2)\n#print(leg)\n\nif sum(leg)+dist+1!=n:\n    print(-1)\n    return\n\nans=[]\nans.append(1)\nu=2\nfor l in leg:\n    for v in range(u+1,u+1+l):\n        ans.append(v)\n    ans.append(u)\n    u+=l+1\nans.append(u)\n\nleg.reverse()\nans2=[]\nans2.append(1)\nu=2\nfor l in leg:\n    for v in range(u+1,u+1+l):\n        ans2.append(v)\n    ans2.append(u)\n    u+=l+1\nans2.append(u)\n\nif ans2<ans:ans=ans2\nprint(*ans)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: