def dfs3(p, d, G, V):
    s = p[-1]
    if noChildren(s, G): return None
    for n in children(s, G):
        if n in V: continue
        V.append(n)
        if n == d: return p + n
        return dfs3(p + n, d, G, V)

def noChildren(s, G):
    return not s in G

def children(s, G):
    return G[s]

def findSP(p, d, G):
    return dfs3(p, d, G, [p])

def step(msg):
    raw_input(msg)

G = {'A':['B'], 'B':['D', 'C'], 'C':['E'], 'D':['E']}

print 'Path: ' + str(findSP('A', 'E', G))

G2 = {'A':['B'], 'B':['A', 'D', 'C'], 'D':['B', 'E'], 'C':['A', 'E'], 'E':['E']}

print 'Path: ' + str(findSP('A', 'E', G2))

print 'Path: ' + str(findSP('D', 'A', G2))

print 'Path: ' + str(findSP('E', 'A', G2))