class DFS:
    def __init__(self, graph):
        self.graph = graph

    def search(self, start, end):
        self._route = []
        self._visited = [start]

        self._dfs(start, end)
        return self._route

    def _dfs(self, start, end):
        self._route.append(start)
        if start == end:
            return True
        for node in self.graph[start]:
            if node not in self._visited:
                self._visited.append(node)
                if self._dfs(node, end):
                    return True
                self._route.append(start)
        return False

if __name__ == '__main__':
    tree = dict()
    tree['e'] =  ['ll', ' w', 'lo', 'df', '!']
    tree[' w'] = ['e', 'o']
    tree['df'] = ['!', 'll', 'lo']
    tree['d'] =  ['!', 'll', 'up', 'lo', 'e']
    tree['!'] =  ['h', 'up', 'll']
    tree['ll'] = ['o', 'h', 'lo', 'up']
    tree['o'] =  [' w', 'e', 'll', 'r', 'df']
    tree['a'] =  ['bc', 'h', 'df', 'll']
    tree['bc'] = [' w', 'up', 'lo']
    tree['l'] =  ['d', 'a', 'lo', '!', 'o']
    tree['r'] =  ['l', 'lo', 'bc']
    tree['h'] =  ['e', '!', 'd']
    tree['up'] = ['a', 'r', 'd']
    tree['lo'] = ['ll', '!', 'd']

    searcher = DFS(tree)
    route = searcher.search('h', '!')
    print "".join(route)