G1 = [[3],[],[0,1,5],[4],[],[3],[3]]
G2 = [[1,3],[0,6,7,5],[5,4],[0,4],[3,7,5,2],[1,7,4,2],[1,7],[5,1,6,4]]
G3 = [[1,2,4],[3],[3,5],[],[5],[]]
G4 = [[1,2],[3,0],[4,0],[1],[2]]

from collections import deque

def parcoursLargeur(G,s0):
    n = len(G)
    atraiter = deque()
    atraiter.append(s0)
    dejavu = [False for i in range(n)]
    dejavu[s0] = True
    while atraiter != deque() :
        u = atraiter.popleft()
        print(u)
        for v in G[u] :
            if not dejavu[v] :
                atraiter.append(v)
                dejavu[v] = True

def fauxParcoursProfondeur(G,s0):
    n = len(G)
    atraiter = []
    atraiter.append(s0)
    dejavu = [False for i in range(n)]
    dejavu[s0] = True
    while atraiter != [] :
        u = atraiter.pop()
        print(u)
        for v in G[u] :
            if not dejavu[v] :
                atraiter.append(v)
                dejavu[v] = True


def parcoursProfondeur(G,s0):
    n = len(G)
    atraiter = []
    atraiter.append(s0)
    dejavu = [False for i in range(n)]
    while atraiter != [] :
        u = atraiter.pop()
        if not dejavu[u] :
            dejavu[u] = True
            print(u)
            for v in G[u] :
                atraiter.append(v)

def parcoursProfondeurRec(G,s0):
    n = len(G)
    dejavu = [False for i in range(n)]
    def explorer(u):
        dejavu[u] = True
        print(u)
        for v in G[u] :
            if not dejavu[v] :
                explorer(v)
    explorer(s0)