from queue import Queue


class Graph:

    def __init__(self, N):
        self.N = N
        self.E = [[] for _ in range(N)]

    def add_edge(self, u, v):
        self.E[u].append(v)
        # neorientovaný graf = hrana oběma směry
        self.E[v].append(u)

    def get_neighbors(self, u):
        return self.E[u]

    def dfs(self, s):
        self.visited = [False] * self.N
        self._dfs(s)

    def _dfs(self, u):
        print(u)
        self.visited[u] = True

        for v in self.get_neighbors(u):
            if not self.visited[v]:
                self._dfs(v)

    def bfs(self, s):
        self.visited = [False] * self.N

        q = Queue()
        q.put(s)
        self.visited[s] = True

        while not q.empty():
            u = q.get()

            print(u)

            for v in self.get_neighbors(u):
                if not self.visited[v]:
                    self.visited[v] = True
                    q.put(v)


if __name__ == '__main__':

    G = Graph(6)
    G.add_edge(0, 1)
    G.add_edge(0, 2)
    G.add_edge(1, 3)
    G.add_edge(1, 2)
    G.add_edge(2, 4)
    G.add_edge(2, 3)
    G.add_edge(3, 5)
    G.add_edge(4, 5)

    #G.dfs(0)
    G.bfs(0)