class Queue:
    def __init__(self, n):
        self.S = [None] * n
        self.n = n
        self.elements = 0
        self.head = 0

    def enqueue(self, x):
        self.S[(self.head + self.elements) % self.n] = x
        self.elements += 1

    def dequeue(self):
        a = self.S[self.head]
        self.head = (self.head + 1) % self.n
        self.elements -= 1
        return a

    def is_empty(self):
        return self.elements == 0


class pkt:
    def __init__(self, nr):
        self.nr = nr
        self.visited = False
        self.d = -1
        self.parent = None


class graf:
    def __init__(self):
        self.arr = []


def BFS(G, s):
    Q = Queue(len(G))
    Graf = graf()
    F = [[] for _ in range(len(G))]
    for i in range (len(G)):
        F[i] = [None] * (2)
    for i in range(len(G)):
        x = pkt(i)
        Graf.arr.append(x)
    Graf.arr[s].d = 0
    Graf.arr[s].visited = True
    Q.enqueue(Graf.arr[s])
    while not Q.is_empty():
        u = Q.dequeue()
        for i in range(len(G)):
            if G[u.nr][i] == 1: # znaczy że z wierzchołka u idzie krawędz do wierzchołka i
                if not Graf.arr[i].visited:
                    Graf.arr[i].visited = True
                    Graf.arr[i].d = u.d + 1
                    Graf.arr[i].parent = u.nr
                    Q.enqueue(Graf.arr[i])
    for i in range (len(G)):                                           #|
        if Graf.arr[i].visited == False:                               #|
            Q.engueue(Graf.arr[i])                                     #|
            while not Q.is_empty():                                    #|
                u = Q.dequeue()                                        #|
                for i in range(len(G)):                                #|
                    if G[u.nr][i] == 1:                                #|Cała ta część jest dla przypadku gdy graf jest niespójny
                        if not Graf.arr[i].visited:                    #|
                            Graf.arr[i].visited = True                 #|
                            Graf.arr[i].d = -1                         #|niepotrzebna linijka ale ustawiam (ponownie) na -1 żeby zaznaczyć że nie da się dojść z wierzchołka s do tego wierzchołka
                            Graf.arr[i].parent = u.nr                  #|
                            Q.enqueue(Graf.arr[i])                     #|
    for i in range(len(G)):
        F[i][0]=Graf.arr[i].parent
        F[i][1]=Graf.arr[i].d
    return F


G = [[0, 1, 1, 0],
     [0, 0, 0, 1],
     [0, 1, 0, 1],
     [0, 0, 0, 0]]
print(BFS(G,0))