def bfs(G,s) :
	P,Q={s :None},[s]
	while Q :
		u=Q.pop(0)
		for v in G[u] :
			if v in P : continue
			P[v]=u
			Q.append(v)
	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']


P = bfs(G,'b')
print(P)