Problem:


Score : 900 points

Problem Statement

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 1

6
1 2
1 3
1 4
1 5
5 6

Sample Output 1

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.

Sample Input 2

6
1 2
2 3
3 4
1 5
5 6

Sample Output 2

1 2 3 4 5 6

Sample Input 3

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

Sample Output 3

-1



Sample input:
6
1 2
1 3
1 4
1 5
5 6


Sample output:
1 2 4 5 3 6

Submission status: Wrong Answer

Solution code:
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)

def far(u,pu=-1,d=0):
    res_u,res_d=u,d
    for v in to[u]:
        if v==pu:continue
        u0,d0=far(v,u,d+1)
        if d0>res_d:
            res_d=d0
            res_u=u0
    return res_u,res_d

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

def makepath(u,pu,t):
    for v in to[u]:
        if v==pu:continue
        path.append(v)
        if v==t or makepath(v,u,t):return True
        path.pop()
    return False

path=[s]
makepath(s,-1,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)
    exit()

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)
print(*ans)

Submission status: Wrong Answer

Solution code:
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]

from collections import deque

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

def far(u,pu=-1,d=0):
    res_u,res_d=u,d
    for v in to[u]:
        if v==pu:continue
        u0,d0=far(v,u,d+1)
        if d0>res_d:
            res_d=d0
            res_u=u0
    return res_u,res_d

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

def makepath(u,pu,t):
    for v in to[u]:
        if v==pu:continue
        path.append(v)
        if v==t or makepath(v,u,t):return True
        path.pop()
    return False

path=[s]
makepath(s,-1,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)
    exit()

ans=deque()
ans.append(1)
u=2
for l in leg:
    ans.append(u)
    u+=1
    for _ in range(l):
        ans.appendleft(u)
        u+=1
ans.append(u)
print(*ans)

Submission status: Wrong Answer

Solution code:
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:
    exit(print(1,2))

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])==1+leafcnt[v] and len(edge[v])!=1:
        if not line:
            check=line_check(v)
            if not check:
                exit(print(-1))
        else:
            exit(print(-1))


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)

Submission status: Wrong Answer

Solution code:
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]
if Dia <= 2:
    print(*list(range(1, N+1)))
else:
    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))

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
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(v,parent,next_p,arr):
    next_v = None
    V1 = []
    V2 = []
    for w in graph[v]:
        if w == parent:
            continue
        if deg[w] == 1:
            V1.append(w)
        else:
            V2.append(w)
    if len(V1) == 0 and len(V2) == 0:
        arr.append(next_p)
        return
    if len(V2) > 0:
        next_v = V2[0]
    else:
        next_v = V1[-1]
        V1 = V1[:-1]
    arr += list(range(next_p+1,next_p+len(V1)+1))
    arr.append(next_p)
    next_p += len(V1)+1
    #create_perm(next_v,v,next_p,arr)

P = []
create_perm(diag[1],None,1,P)

Q = []
create_perm(diag[0],None,1,Q)

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

Submission status: Wrong Answer

Solution code:
import sys
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

Submission status: Wrong Answer

Solution code:
#!/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 + 1)] + [2]
        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)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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)

def far(u,pu=-1,d=0):
    res_u,res_d=u,d
    for v in to[u]:
        if v==pu:continue
        u0,d0=far(v,u,d+1)
        if d0>res_d:
            res_d=d0
            res_u=u0
    return res_u,res_d

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

def makepath(u,pu,t):
    for v in to[u]:
        if v==pu:continue
        path.append(v)
        if v==t or makepath(v,u,t):return True
        path.pop()
    return False

path=[s]
makepath(s,-1,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)
    exit()

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)

Submission status: Accepted

Solution code:
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)
    exit()

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)

Submission status: Accepted

Solution code:
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:
    exit(print(1,2))

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:
                exit(print(-1))
        else:
            exit(print(-1))


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)

Submission status: Accepted

Solution code:
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(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 = map(int, line.split())
    v -= 1
    w -= 1
    links[v].add(w)
    links[w].add(v)

print(*solve(n, links))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!/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)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
#define MAXN 100100

int A[MAXN];
vi V[MAXN];
vi V2[MAXN];
int N,a,b;
vpi E;
vi l,res;

void dfs(int x, int p){
	l.pb(A[x]);
	for (auto v:V[x])if(v!=p && A[v]){
		dfs(v,x);
	}
}

int main(){
	cin>>N;
	if (N == 2){
		cout<<"1 2";
		return 0;
	}
	for (int i=1;i<N;++i){
		cin>>a>>b;
		E.pb(a,b);
		V[a].pb(b);V[b].pb(a);
	}
	for (auto i : E){
		if (SZ(V[i.f]) == 1){
			++A[i.s];
		}else if(SZ(V[i.s]) == 1){
			++A[i.f];
		}
	}
	for (auto i : E){
		if (!A[i.f] || !A[i.s])continue;
		V2[i.f].pb(i.s);
		V2[i.s].pb(i.f);
	}
	for (int i=1;i<=N;++i)if(SZ(V2[i]) > 2){
		cout<<-1;
		return 0;
	}
	for (int i=1;i<=N;++i){
		if (A[i] == 1){
			dfs(i,-1);
		}
	}
	if (SZ(l) == 0)assert(0);
	// for (auto i : l)cout<<i<<' ';cout<<'\n';
	int t = 1;
	for (auto i:l){
		for (int k=t+i;k>t;--k){
			res.pb(k);
		}
		res.pb(t);
		t = t+i+1;
	}
	for (auto i:res)cout<<i<<' ';cout<<'\n';
}

Submission status: Runtime Error

Solution code:
import sys
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(v,parent,next_p,arr):
    next_v = None
    V1 = []
    V2 = []
    for w in graph[v]:
        if w == parent:
            continue
        if deg[w] == 1:
            V1.append(w)
        else:
            V2.append(w)
    if len(V2) > 0:
        next_v = V2[0]
    else:
        if len(V1) == 0:
            arr.append(next_p)
            return
        next_v = V1[-1]
        V1 = V1[:-1]
    arr += list(range(next_p+1,next_p+len(V1)+1))
    arr.append(next_p)
    next_p += len(V1)+1
    create_perm(next_v,v,next_p,arr)

P = []
create_perm(diag[1],None,1,P)

Q = []
create_perm(diag[0],None,1,Q)

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

Submission status: Runtime Error

Solution code:
import sys
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(v,parent,next_p,arr):
    next_v = None
    V1 = []
    V2 = []
    for w in graph[v]:
        if w == parent:
            continue
        if deg[w] == 1:
            V1.append(w)
        else:
            V2.append(w)
    if len(V1) == 0 and len(V2) == 0:
        arr.append(next_p)
        return
    if len(V2) > 0:
        next_v = V2[0]
    else:
        next_v = V1[-1]
        V1 = V1[:-1]
    arr += list(range(next_p+1,next_p+len(V1)+1))
    arr.append(next_p)
    next_p += len(V1)+1
    create_perm(next_v,v,next_p,arr)

P = []
create_perm(diag[1],None,1,P)

Q = []
create_perm(diag[0],None,1,Q)

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

Submission status: Runtime Error

Solution code:
import sys
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(v,parent,next_p,arr):
    next_v = None
    V1 = []
    V2 = []
    for w in graph[v]:
        if w == parent:
            continue
        if deg[w] == 1:
            V1.append(w)
        else:
            V2.append(w)
    if len(V1) == 0 and len(V2) == 0:
        arr.append(next_p)
        return
    if len(V2) > 0:
        next_v = V2[0]
    else:
        next_v = V1.pop()
    arr += list(range(next_p+1,next_p+len(V1)+1))
    arr.append(next_p)
    next_p += len(V1)+1
    create_perm(next_v,v,next_p,arr)

P = []
create_perm(diag[1],None,1,P)

Q = []
create_perm(diag[0],None,1,Q)

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

Submission status: Runtime Error

Solution code:
import sys
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(v,parent,next_p,arr):
    next_v = None
    V1 = []
    V2 = []
    for w in graph[v]:
        if w == parent:
            continue
        if deg[w] == 1:
            V1.append(w)
        else:
            V2.append(w)
    if len(V1) == len(V2) == 0:
        arr.append(next_p)
        return
    next_v = V2[0] if V2 else V1.pop()
#    arr += list(range(next_p+1,next_p+len(V1)+1))
#    arr.append(next_p)
#    next_p += len(V1)+1
    create_perm(next_v,v,next_p,arr)

P = []
create_perm(diag[1],None,1,P)

Q = []
create_perm(diag[0],None,1,Q)

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