from collections import deque

class Vertex:
    def __init__(self):
        self.visited = False
        self.d = None # dystans tanego wierzchołka od roota
        self.parent = None
        self.pos = None

def BFS(G, s):
    Q = deque()
    n = len(G[0])
    V = n * [None]
    for i in range(n):
        V[i].pos = i
    V[s].d = 0
    V[s].visited = True
    #V[s].parent = None  nie potrzebne po przejsciu pętli
    #V[s].pos = s
    Q.appendleft(V[s])
    while (len(Q) > 0):
        u = Q.pop()
        for j in range(n):
            if(G[u.pos][j] == 1):
                if(not V[j].visited):
                    V[j].visited = True
                    V[j].d = u.d + 1
                    V[j].parent = u.pos
                    Q.put(V[j])
    Wynik = n * [None]
    for i in range(n):
        Wynik[i][0] = V[i].parent
        Wynik[i][1] = V[i].d
    return Wynik;

    BFS([[0,1,1,0],[0,0,0,1],[0,1,0,1],[0,0,0,0]] , 0)