【DFS・BFS】グラフ（木構造）における２頂点間の経路を求める【Python】

from collections import deque

N, X, Y = map(int, input().split())

# 木の情報を2次元リストに格納
g = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

q = deque()
q.append(X - 1)
upper = [-1] * N
# 頂点Aは根であることを, -2で表現する
upper[X - 1] = -2

def BFS():
    while q:
        # 先頭を取り出してnowとする
        now = q.popleft()
        # nowと隣接する要素nxtをすべて調べる
        for nxt in g[now]:
            # 未訪問なら"nxtの1つ前の要素"=nowを記録する
            if upper[nxt] == -1:
                upper[nxt] = now
                q.append(nxt)
BFS()
                
ans = []
now = Y - 1

while upper[now] != -2:
    ans.append(now)
    now = upper[now]

ans.append(now)
# ansにはB=>Aとたどる経路を格納したので, 逆順に出力する
for i in ans[::-1]:
    print(i + 1, end=" ")

# 再帰回数の上限を増やしておく必要がある
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

# 木の情報を2次元リストに格納
N, X, Y = map(int, input().split())
X, Y = X - 1, Y - 1
g = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
    
# 地点 i の１つ前（の深さ）の地点
prev = [-1] * N
# DFS(今いる場所n, 前にいた場所p)
def DFS(n, p):
    # 今いる場所から、行ける場所
    for nv in g[n]:
        # 行ける所が前にいた場所ならスルー
        if nv == p:
            continue
        # 行ける場所に対する「前の場所」として現地点nを格納
        prev[nv] = n
        # 行ける場所=>今いる場所/今いる場所=>前にいた場所
        DFS(nv, n)

# 前にいた場所は適当に-1としておく        
DFS(Y, -1)
# 出力のための操作
now = X
path = [X + 1]
while prev[now] != -1:
    # さかのぼっていく
    now = prev[now]
    path.append(now + 1)
print(*path)