def dfs(s, adj):
    xs = [s]
    visited = set()
    while xs:
        u = xs.pop()
        if u not in visited:
            print(u)
            visited.add(u)
            for v in adj.get(u, []):
                xs.append(v)

def bfs(s, adj):
    xs = [s]
    visited = set()
    while xs:
        u = xs.pop(0)
        if u not in visited:
            print(u)
            visited.add(u)
            for v in adj.get(u, []):
                xs.append(v)