#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue May 14 17:24:32 2024

@author: ***
"""

L1 = [[1, 2], [6], [3, 4], [], [7, 8], [1], [], [], [6]]
D1 = {0: [1,2], 1: [6], 2: [3, 4], 3: [0], 4: [7, 8], 5: [1], 6: [0], 7: [0], 8: [6]}
L2 = [[1,3],[0,2,4],[1,5],[0,4,6],[1,3,5,7],[2,4,8],[3,7],[4,6,8],[5,7]]
D2 = {0: [1,3], 1: [0,2,4], 2:[1,5], 3: [0,4,6], 4:[1,3,5,7], 5: [2,4,8],\
      6: [3,7], 7:[4,6,8], 8:[5,7]}

from collections import deque



def BFS(LA, s):
    # votre code. L'instruction suivante pourra alors être retirée...
    pass

def DFS(LA, s):
    # votre code
    pass
    
# version récursive        
def DFS2(LA, s):
    vus = []
    def DFSrec(LA, s, vus):
        parcours = [s]
        # votre code
        return parcours
    
    return DFSrec(LA, s, vus)

def cheminBFS(LA, s1, s2):
    # votre code
    pass

def cheminDFS(LA, s1, s2):
    # votre code
    pass