여러개의 테스트 케이스에 대해서 맞다고 나오는데 왜 틀릴까요 ㅠㅠ

import sys
sys.setrecursionlimit(100000)

a, b, c = map(int, input().split())
lst = list(map(lambda x: x.strip(), sys.stdin.readlines()))
finish_dfs = []
finish_bfs = set([])
dic= {}

for line in lst :
    e,f = map(int, line.split())
    
    if e in dic :
        dic[e].append(f)
    else :
        dic[e] = [f]

    if f in dic :
        dic[f].append(e)
    else :
        dic[f] = [e]

def dfs(val) :
    print(val, end=" ")
    finish_dfs.append(val)
    
    temp=sorted(list(dic[val]))
    [dfs(x) for x in temp if x not in finish_dfs]

def bfs(val) :
    lst = [val]
    
    while lst :
        finish_bfs.update(lst)
        [print(idx, end=" ") for idx in lst]

        temp = sorted(list(lst))
        lst = []
        for idx in temp :
            lst.extend(sorted([x for x in dic[idx] if (x not in lst) and (x not in finish_bfs)]))
        
dfs(c)
print("")
bfs(c)