import random

def dfs(G,s) :
	P,Q={s :None},[s]
	while Q :
		u=Q[-1]
		R=[y for y in G[u] if y not in P]
		if R :
			v=random.choice(R)
			P[v]=u
			Q.append(v)
		else :
			Q.pop()
	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'))