class Graphe:
    def __init__(self):
        self.sommets = {}

    def edge(self, u, v):
        if v not in self.sommets:
            self.sommets[v] = []
        if u not in self.sommets:
            self.sommets[u] = []
        if v not in self.sommets[u]:
            self.sommets[u].append(v)
        if u not in self.sommets[v]:
            self.sommets[v].append(u)

    def mystere(self):
        from collections import deque
        sortie = []
        tmp = deque()
        tmp.append('NA')
        while tmp:
            S = tmp.popleft()
            if S not in sortie:
                sortie.append(S)
                unvisited = [n for n in self.sommets[S] if n not in sortie]
                tmp.extend(unvisited)
        return sortie

    def mat(self):
        A = [ [0] * len(self.sommets) for i in range( len(self.sommets) )] 
        S = sorted( list( self.sommets.keys() ) )
        for nom in S:
            for i in self.sommets[nom]:
                A[ S.index(nom) ][ S.index(i) ] = 1
        return A
            

G = Graphe()
liste = [ 'ARA' , 'B' , 'BFC' , 'C' , 'CVL' , 'GE' , 'HDF' , 'IDF' , 'N' , 'NA' , 'O' , 'PACA' , 'PDL']
for i in liste:
    if i == 'ARA':
        L = ['BFC' , 'CVL' , 'NA' , 'O']
    elif i == 'B':
        L = ['N' , 'PDL']
    elif i == 'BFC':
        L = ['GE','IDF','CVL','ARA']
    elif i == 'C':
        L = ['PACA']
    elif i == 'CVL':
        L = ['ARA' , 'BFC' , 'IDF' , 'N' , 'NA' , 'PDL']
    elif i == 'GE':
        L = ['BFC' , 'HDF' , 'IDF']
    elif i == 'HDF':
        L = ['GE' , 'IDF', 'N']
    elif i == 'IDF':
        L = ['BFC' , 'CVL' , 'GE' , 'HDF' , 'N']
    elif i == 'N':
        L = ['B' , 'CVL' , 'IDF' , 'HDF' , 'PDL']
    elif i == 'NA':
        L = ['ARA' , 'CVL' , 'O' , 'PDL']
    elif i == 'O':
        L = ['ARA' , 'NA' , 'PACA']
    elif i == 'PACA':
        L = ['ARA' , 'C' , 'O']
    elif i == 'PDL':
        L = ['B', 'CVL', 'N', 'NA']

    for j in L:
        G.edge(j , i)

# affichage du graphe
for key,value in G.sommets.items():
    print(key , ':' , value)

# parcours du graphe
print( G.mystere() )

# affichage de la matrice d'adjacence
for i in G.mat():
    print(i)
