from collections import defaultdict

# This class represents a directed graph using adjacency list representation
class Graph:

    def __init__(self, edges=[]):
        # default dictionary to store graph
        self.graph = defaultdict(list)
        for e in edges:
            self.addEdge(*e)

    def addEdge(self, u, v):
        self.graph[u].append(v)
        return

    # Function to print a BFS of graph
    def BFS(self, s):
        # use set to track visited vertices
        visited = set()
        # use queue for BFS
        queue = []

        # begin search with source node
        queue.append(s)
        visited.add(s)

        while queue:
            s = queue.pop(0)
            print(s, end=" ")
            # search all adjacent vertices
            for i in self.graph[s]:
                if i not in visited:
                    queue.append(i)
                    visited.add(i)
        return


if __name__ == '__main__':
    g = Graph()
    edges = [
        (1, 2), (1, 3), (1, 4), (2, 5), (2, 6), (5, 9),
        (5, 10), (4, 7), (4, 8), (7, 11), (7, 12)
    ]
    g = Graph(edges)
    start_vertex = 1

    print("Breadth First Traversal (starting from vertex {})".format(start_vertex))
    g.BFS(start_vertex)





# alternate implementation

# from collections import deque
# import helpers.graph as graph_class
#
#
# # Perform BFS on the graph starting from vertex `v`
# def BFS(graph, v, discovered):
#     # create a queue for doing BFS
#     q = deque()
#
#     # mark the source vertex as discovered
#     discovered[v] = True
#
#     # enqueue source vertex
#     q.append(v)
#
#     # loop till queue is empty
#     while q:
#
#         # dequeue front node and print it
#         v = q.popleft()
#         print(v, end=' ')
#
#         # do for every edge (v, u)
#         for u in graph.adjList[v]:
#             if not discovered[u]:
#                 # mark it as discovered and enqueue it
#                 discovered[u] = True
#                 q.append(u)
#
#
#
# if __name__ == '__main__':
#
#     # List of graph edges as per the above diagram
#     edges = [
#         (1, 2), (1, 3), (1, 4), (2, 5), (2, 6), (5, 9),
#         (5, 10), (4, 7), (4, 8), (7, 11), (7, 12)
#         # vertex 0, 13, and 14 are single nodes
#     ]
#
#     # total number of nodes in the graph (labelled from 0 to 14)
#     n = 15
#
#     # build a graph from the given edges
#     graph = graph_class.Graph(edges, n)
#
#     # to keep track of whether a vertex is discovered or not
#     discovered = [False] * n
#
#     # Perform BFS traversal from all undiscovered nodes to
#     # cover all connected components of a graph
#     for i in range(n):
#         # print("checking i: {}".format(i))
#         if not discovered[i]:
#             # print("not discovered i: {}".format(i))
#             # start BFS traversal from vertex i
#             BFS(graph, i, discovered)
#
#
#
#
# # """
# # OUTPUT
# # 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
# # """