DFS

n=list(map(int,input().split()))
land=n[0]
bridge=n[1]
start=n[2]
bridegeinfo=[]
footprint=[]
visited=[0]*land
for i in range(bridge):
    li=tuple(map(int,input().split()))
    bridegeinfo.append(li[:])
visited[start-1]=1
footprint.append(start)
def DFS(start):
    visited[start-1]=1 #시작점은 방문했다
    #footprint.append(start)
    for i in bridegeinfo: #리스트 전체 탐색
        if i[0]==start and visited[i[1]-1]==0: #아직 방문 안 한 곳이라면
            visited[i[1]-1]=1 #방문기록
            footprint.append(i[1]) #방문기록
            next=i[1]
            DFS(next)
            #재귀끝내고와서 백트래킹으로 다시 원래
    return
DFS(start)
print(footprint)

그 백트래킹하는 게 중요...
(1,2) (2,3) (1,4) (1,3) (2,4)

이렇게 뒤죽박죽이어도 1 갔다가 2 갔다가 3 갔다가 다음이 없으니까 다시 2로 돌아오는!!!!게 제일 중요하지 그게 FOR에서 계속하고 있는 거고 돌아가면 다시 START는 2니까
탐색은 순서대로 하고있으니...(1,2) (2,3) ...

BFS까지 근데 간선 양방향이네

이건 일방향

n=list(map(int,input().split()))
land=n[0]
bridge=n[1]
start=n[2]
bridegeinfo=[]
footprint=[]
footprint1=[]
visited=[0]*land
visited1=[0]*land
for i in range(bridge):
    li=tuple(map(int,input().split()))
    bridegeinfo.append(li[:])
visited[start-1]=1
visited1[start-1]=1
footprint.append(start)
footprint1.append(start)#함수 전에 와야 마지막 경로가 중복 저장이 안 됨
def DFS(start):
    visited[start-1]=1 #시작점은 방문했다
    #footprint.append(start)
    for i in bridegeinfo: #리스트 전체 탐색
        if i[0]==start and visited[i[1]-1]==0: #아직 방문 안 한 곳이라면
            visited[i[1]-1]=1 #방문기록
            footprint.append(i[1]) #방문기록
            next=i[1]
            DFS(next)
            #재귀끝내고와서 백트래킹으로 다시 원래
            
    return

count=0
def BFS(start):
    global count
    execu=0
    visited1[start-1]=1
    
    for i in bridegeinfo:
        if i[0]==start and i[1] not in footprint1:
            visited1[i[1]-1]=1
            footprint1.append(i[1])
            count+=1
            execu+=1
    if execu:
        for j in footprint1[count:]:
            BFS(j) #start인 거는 한 번씩 돌아주고 다음 거
    return

DFS(start)
BFS(start)
print(footprint)
print(footprint1)

n=list(map(int,input().split()))
land=n[0]
bridge=n[1]
start=n[2]
bridegeinfo=[]
footprint=[]

visited=[0]*land

for i in range(bridge):
    li=tuple(map(int,input().split()))
    bridegeinfo.append(li[:])
visited[start-1]=1

footprint.append(start)
#함수 전에 와야 마지막 경로가 중복 저장이 안 됨
def DFS(start):
    visited[start-1]=1 #시작점은 방문했다
    #footprint.append(start)
    for i in bridegeinfo: #리스트 전체 탐색
        if i[0]==start and visited[i[1]-1]==0: #아직 방문 안 한 곳이라면
            visited[i[1]-1]=1 #방문기록
            footprint.append(i[1]) #방문기록
            next=i[1]
            DFS(next)
            #재귀끝내고와서 백트래킹으로 다시 원래
            
    return

footprint1=[]
footprint1.append(start)
visited1=[0]*land
visited1[start-1]=1
count=0
def BFS(start): #BFS도 재귀로 할 수는,,,있..?
    global count
    execu=0 #실행했는지 start가 무언가와 이어져있는지
    visited1[start-1]=1
    
    for i in bridegeinfo:
        if i[0]==start and i[1] not in footprint1:
            visited1[i[1]-1]=1
            footprint1.append(i[1])
            count+=1
            execu+=1
    if execu: #만약 2가 start이었다면 이어진 데가 없음 그럼 footprint에 들어온 게 없음 2의 목적지부터 하고자시고 안 해도 됨
        for j in footprint1[count:]: #start가 방문했던 데부터
            BFS(j) #start인 거는 한 번씩 돌아주고 다음 거
    return

DFS(start)
BFS(start)
print(footprint)
print(footprint1)