[백준 1260] DFS와 BFS

def DFS(G,sp):
    lst=[1]*len(G)
    lst[0]=0
    asn=[]
    asn=DFG_recursion(G,sp,lst,asn)
    return asn
    
def DFG_recursion(G,p,lst,asn):
    lst[p]=0
    asn.append(p)
    k=len(G[p])
    l=[]
    for i in range(k):
        l.append(G[p][i])
    l=sorted(l)
    for i in l:
        if lst[i]!=0:
            DFG_recursion(G,i,lst,asn)
    return asn

import queue
def BFS(G,sp):
    que=queue.Queue()
    lst=[1]*len(G)
    lst[0]=0
    ans=[]
    p=sp
    que.put(sp)
    lst[sp]=0
    while que.qsize():
        p=que.get()
        ans.append(p)
        k=len(G[p])
        l=[]
        for i in range(k):
            if lst[G[p][i]]!=0:
                l.append(G[p][i])
        l=sorted(l)
        for i in l:
            if lst[i]!=0:
                lst[i]=0
                que.put(i)
    return ans

v,e,sp=map(int, input().split())
G=[[] for _ in range(v+1)]

for i in range(e):
    a,b=map(int, input().split())
    if a==b:
        G[a].append(b)
    else :
        G[a].append(b)
        G[b].append(a)

print(*DFS(G,sp))
print(*BFS(G,sp))