class node:
    def __init__(self, n):
        self.parent = None
        self.d = 0
        self.visited = False
        self.numer = n

class queue:
    def __init__(self):
        self.arr = []
        self.elements = 0
        self.head = 0

    def put(self, val):
        self.arr.append(val)
        self.elements += 1

    def get(self):
        res = self.arr[self.head]
        self.head += 1
        self.elements -= 1
        return res

    def is_empty(self):
        if self.elements == 0:
            return True
        return False




def BFS(G, s):
        # G -> macierz opisująca graf G: G[i][j]==1 jeśli jest
        # wierzchołek z i do j. W przeciwnym razie G[i][j]=0
        # s to numer wierzchołka źródłowego
        n = len(G)
        Q = queue()  # nasza kolejka

        # teraz musimy jakos wierzcholki zareprezentowac:
        N = [0] * n  # lista wierzcholków
        for i in range(0, n):
            N[i] = node(i)  # ustawiamy jak na wykładzie

        Q.put(N[s])

        while not Q.is_empty():
            u = Q.get()
            for v in N:  # lecimy po strukturze wierzchołków
                if G[u.numer][v.numer] == 1:
                    if not v.visited:
                        v.visited = True
                        v.d = u.d + 1
                        v.parent = u
                        Q.put(v)

        maks = 0
        z = 0
        for i in range(0, len(N)):
            if N[i].d > maks:
                maks = i
                z = maks

        res = [[0, 0]] * (z + 1)
        tmp = node(i)
        tmp = N[z]
        z = z - 1
        while z >= 0:
            y = tmp.parent
            res[z][0] = y.numer
            res[z][1] = tmp.numer
            tmp = tmp.parent
            z -= 1
        return res

G = [[0,1,1,0],[0,0,0,1],[0,1,0,1], [0,0,0,0]]

print( BFS(G,0) )