import random


class Maillon:

	def __init__(self, valeur, suivant=None):
		self.valeur = valeur
		self.suivant = suivant



class Pile:

	def __init__(self):
		self.taille = 0 # nombre d'assiettes dans la pile
		self.sommet = None


	def empiler(self, valeur):
		self.sommet = Maillon(valeur, self.sommet)
		self.taille += 1

	def depiler(self):
		if self.taille > 0:
			valeur = self.sommet.valeur
			self.sommet = self.sommet.suivant
			self.taille -= 1
			return valeur

	def estVide(self):
		return self.taille == 0


	def lireSommet(self):
		return self.sommet.valeur

 

 



def dfs(G,s) :
	P = {s: None} 
	Q = Pile()
	Q.empiler(s)
	while not(Q.estVide()) :
		u = Q.lireSommet()
		R=[y for y in G[u] if y not in P]
		if R :
			v=random.choice(R)
			P[v]=u
			Q.empiler(v)
		else :
			Q.depiler()
	return P

 
	
	
G=dict()
G['a']=['b','c']
G['b']=['a','d','e']
G['c']=['a','d']
G['d']=['b','c','e']
G['e']=['b','d','f','g']
G['f']=['e','g']
G['g']=['e','f','h']
G['h']=['g']


print(dfs(G,'g'))