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.

Difficulty: competition

Starter code:

Solutions:
import sys
from collections import deque


def diameter(n, links):
    q = deque([(0, -1)])
    v = 0
    while q:
        v, p = q.popleft()
        q.extend((u, v) for u in links[v] if u != p)

    q = deque([(v, -1)])
    w = 0
    parents = [-1] * n
    while q:
        w, p = q.popleft()
        parents[w] = p
        q.extend((u, w) for u in links[w] if u != p)
    parents_rev = [-1] * n
    p = w
    while parents[p] != -1:
        parents_rev[parents[p]] = p
        p = parents[p]
    return v, w, parents, parents_rev


def construct(s, links, parents, parents_rev):
    v = s
    result = []
    while v != -1:
        pv, rv = parents[v], parents_rev[v]
        child_count = 0
        for u in links[v]:
            if u == pv or u == rv:
                continue
            if len(links[u]) != 1:
                return False
            child_count += 1
        my_value = len(result) + 1
        result.extend(list(range(my_value + 1, my_value + child_count + 1)))
        result.append(my_value)
        v = parents[v]
    return result


def solve(n, links):
    d1, d2, parents, parents_rev = diameter(n, links)
    result1 = construct(d1, links, parents_rev, parents)
    if result1 is False:
        return [-1]
    result2 = construct(d2, links, parents, parents_rev)
    return min(result1, result2)


n = int(input())
links = [set() for _ in range(n)]
INF = 10 ** 9

for line in sys.stdin:
    v, w = list(map(int, line.split()))
    v -= 1
    w -= 1
    links[v].add(w)
    links[w].add(v)

print((*solve(n, links)))


import sys

#sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n=II()
to=[[] for _ in range(n)]
for _ in range(n-1):
    u,v=MI1()
    to[u].append(v)
    to[v].append(u)
#print(to)

def far(u):
    stack=[(u,-1,0)]
    mxd=mxu=-1
    while stack:
        u,pu,d=stack.pop()
        if d>mxd:
            mxd=d
            mxu=u
        for v in to[u]:
            if v==pu:continue
            stack.append((v,u,d+1))
    return mxu,mxd

s,_=far(0)
t,dist=far(s)
#print(s,t,dist)

def makepath(u,t):
    stack=[(u,-1)]
    while stack:
        u,pu=stack.pop()
        while path and path[-1]!=pu:path.pop()
        path.append(u)
        if u==t:return
        for v in to[u]:
            if v==pu:continue
            stack.append((v,u))

path=[s]
makepath(s,t)
#print(path)

leg=[]
for u in path[1:-1]:leg.append(len(to[u])-2)
#print(leg)

if sum(leg)+dist+1!=n:
    print(-1)
    return

ans=[]
ans.append(1)
u=2
for l in leg:
    for v in range(u+1,u+1+l):
        ans.append(v)
    ans.append(u)
    u+=l+1
ans.append(u)

leg.reverse()
ans2=[]
ans2.append(1)
u=2
for l in leg:
    for v in range(u+1,u+1+l):
        ans2.append(v)
    ans2.append(u)
    u+=l+1
ans2.append(u)

if ans2<ans:ans=ans2
print(*ans)


import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

N = int(input())
VW = [[int(x)-1 for x in input().split()] for _ in range(N-1)]

"""
直径に次数1の頂点が生えている
"""

graph = [[] for _ in range(N)]
deg = [0] * N
for v,w in VW:
    graph[v].append(w)
    graph[w].append(v)
    deg[v] += 1
    deg[w] += 1

def dijkstra(start):
    INF = 10**10
    dist = [INF] * N
    q = [(start,0)]
    while q:
        qq = []
        for v,d in q:
            dist[v] = d
            for w in graph[v]:
                if dist[w] == INF:
                    qq.append((w,d+1))
        q = qq
    return dist

dist = dijkstra(0)
v = dist.index(max(dist))
dist = dijkstra(v)
w = dist.index(max(dist))
diag = v,w

def create_perm(start):
    arr = []
    v = start
    parent = None
    next_p = 1
    while True:
        n = 0
        next_v = None
        for w in graph[v]:
            if w == parent:
                continue
            if next_v is None or deg[next_v] < deg[w]:
                next_v = w
            if deg[w] == 1:
                n += 1
        if next_v is None:
            return arr + [next_p]
        if deg[next_v] == 1:
            n -= 1
        arr += list(range(next_p+1,next_p+n+1))
        arr.append(next_p)
        next_p += n+1
        parent = v
        v = next_v

P = create_perm(diag[1])

Q = create_perm(diag[0])

if len(P) != N:
    answer = -1
else:
    if P > Q:
        P = Q
    answer = ' '.join(map(str,P))
print(answer)



import sys
readline = sys.stdin.readline

def parorder(Edge, p):
    N = len(Edge)
    par = [0]*N
    par[p] = -1
    stack = [p]
    order = []
    visited = set([p])
    ast = stack.append
    apo = order.append
    while stack:
        vn = stack.pop()
        apo(vn)
        for vf in Edge[vn]:
            if vf in visited:
                continue
            visited.add(vf)
            par[vf] = vn
            ast(vf)
    return par, order

def getcld(p):
    res = [[] for _ in range(len(p))]
    for i, v in enumerate(p[1:], 1):
        res[v].append(i)
    return res

def dfs(St):
    dist = [0]*N
    stack = St[:]
    used = [False]*N
    for s in St:
        used[s] = True
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if not used[vf]:
                used[vf] = True
                dist[vf] = 1 + dist[vn]
                stack.append(vf)
    return dist

N = int(readline())
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)

dist0 = dfs([0])
fs = dist0.index(max(dist0))
distfs = dfs([fs])
en = distfs.index(max(distfs))
disten = dfs([en])

Dia = distfs[en]
path = []
for i in range(N):
    if distfs[i] + disten[i] == Dia:
        path.append(i)

if max(dfs(path)) > 1:
    print(-1)
else:
    
    path.sort(key = lambda x: distfs[x])
    
    cnt = 1
    hold = 0
    perm1 = [None]*N
    onpath = set(path)
    idx = 0
    for i in range(Dia+1):
        vn = path[i]
        hold = 0
        for vf in Edge[vn]:
            if vf in onpath:
                continue
            hold += 1
            perm1[idx] = cnt + hold
            idx += 1
        perm1[idx] = cnt
        idx += 1
        cnt = cnt+hold+1
    
    cnt = 1
    hold = 0
    perm2 = [None]*N
    onpath = set(path)
    idx = 0
    for i in range(Dia+1):
        vn = path[Dia-i]
        hold = 0
        for vf in Edge[vn]:
            if vf in onpath:
                continue
            hold += 1
            perm2[idx] = cnt + hold
            idx += 1
        perm2[idx] = cnt
        idx += 1
        cnt = cnt+hold+1
    print(*min(perm1, perm2))

#!/usr/bin/env python3


def solve(n, adj_list, d):

    s = []
    path_adj_list = [[] for _ in range(n)]
    for v in range(n):
        if 1 < d[v]:
            p = path_adj_list[v]
            for w in adj_list[v]:
                if 1 < d[w]:
                    p.append(w)
            if 2 < len(p):
                print((-1))
                return
            if len(p) == 1:
                s.append(v)

    if len(s) == 0:
        ans = [1] + [v for v in range(3, n)] + [2]
        if 2 < n:
            ans += [n]
        print((' '.join(list(map(str, ans)))))
        return

    visited = [False] * n
    v, w = s
    while v != w and d[v] == d[w]:
        visited[v] = True
        visited[w] = True
        f = False
        for nv in path_adj_list[v]:
            if not visited[nv]:
                f = True
                v = nv
                break
        if not f:
            break
        f = False
        for nw in path_adj_list[w]:
            if not visited[nw]:
                f = True
                w = nw
                break
        if not f:
            break

    if d[v] > d[w]:
        v = s[1]
    else:
        v = s[0]

    visited = [False] * n
    visited[v] = True
    ans = [1] + [w for w in range(3, d[v] + 1)] + [2]
    c = d[v]
    v = path_adj_list[v][0]
    while True:
        visited[v] = True
        ans += [w for w in range(c + 2, c + d[v])] + [c + 1]
        c += d[v] - 1
        f = False
        for nv in path_adj_list[v]:
            if not visited[nv]:
                f = True
                v = nv
                break
        if not f:
            break

    ans += [n]

    print((' '.join(list(map(str, ans)))))
    return


def main():
    n = input()
    n = int(n)
    adj_list = [[] for _ in range(n)]
    d = [0] * n
    for _ in range(n - 1):
        v, w = input().split()
        v = int(v) - 1
        w = int(w) - 1
        adj_list[v].append(w)
        adj_list[w].append(v)
        d[v] += 1
        d[w] += 1

    solve(n, adj_list, d)


def __starting_point():
    main()


__starting_point()

import sys

input=sys.stdin.readline
sys.setrecursionlimit(2*10**5)

n=int(input())
edge=[[] for i in range(n)]
for i in range(n-1):
    v,w=map(int,input().split())
    edge[v-1].append(w-1)
    edge[w-1].append(v-1)

if n==2:
    print(1,2);return

leafcnt=[0]*n
for v in range(n):
    for nv in edge[v]:
        if len(edge[nv])==1:
            leafcnt[v]+=1

used=[False]*n
line=[]
def line_check(v):
    used[v]=True
    line.append(leafcnt[v])
    flag=False
    for nv in edge[v]:
        if not used[nv] and len(edge[nv])!=1:
            if not flag:
                line_check(nv)
                flag=True
            else:
                return False
    return True

for v in range(n):
    if not used[v] and len(edge[v])-leafcnt[v]<=1 and len(edge[v])!=1:
        if not line:
            check=line_check(v)
            if not check:
                print(-1);return()
        else:
            print(-1);return()


line_rev=line[::-1]
res=min(line,line_rev)
res=[0]+res+[0]
res[1]-=1
res[-2]-=1

ans=[]
L=1
for val in res:
    R=L+val
    for i in range(L+1,R+1):
        ans.append(i)
    ans.append(L)
    L=R+1

print(*ans)