#!/usr/bin/python3
# Abstraktní reprezentace grafu třídou,
# implementace třídy pomocí matice sousednosti

from collections import deque

class Graf:
    """Reprezentace grafu maticí sousednosti."""

    def __init__(self, n):
        self.n = n
        self.matice = [[0]*n for _ in range(n)]

    def __repr__(self):
        return str(self.matice)

    def pridej_hranu(self, i, j):
        self.matice[i][j] = 1

    # Na cyklus přes všechny vrcholy tentokrát potřebujeme vyrobit
    # iterátor. Pozor, nestačí definovat metodu __iter__, protože
    # potřebujeme předat jako parametr vrchol, jehož sousedy chceme
    # vyjmenovat.
    def sousede(self, i):
        return SousedeIt(self, i)

class SousedeIt:
    """Iterátor přes sousedy zadaného vrcholu."""

    def __init__(self, graf, i):
        # Iterátor si pamatuje:
        self.graf = graf    # ke kterému grafu patří
        self.i = i          # sousedy kterého vrcholu vyjmenovává
        self.j = 0          # aktuální polohu

    # Pozor: Pokud napíšeme "for v in graf.sousede(u)", cyklus for bude chtít
    # po objektu vráceném z metody sousede, aby vyrobil svůj iterátor. Jenže
    # v našem případě to už iterátor je, tak ho musíme naučit, aby vrátil sám
    # sebe. To je v Pythonu standardní postup: když iterátoru řeknete, že má
    # vyrobit iterátor, vrátí sebe sama.
    def __iter__(self):
        return self

    # Vrátí dalšího souseda v pořadí
    def __next__(self):
        # Kde je další jednička v řádku?
        while self.j < self.graf.n and self.graf.matice[self.i][self.j] == 0:
            self.j += 1
        if self.j < self.graf.n:
            self.j += 1
            return self.j - 1
        else:
            raise StopIteration


# Původní příklad na prohledávání do šířky jsme přepsali tak,
# aby s grafem pracoval výhradně pomocí třídy Graf.

n = int(input())
graf = Graf(n)
for i in range(n):
    for j in input().split():
        graf.pridej_hranu(i, int(j))

print(graf)

def prohledej(v0):
    byl_jsem = [False] * n
    byl_jsem[v0] = True
    vzdalenost = [None] * n
    vzdalenost[v0] = 0
    fronta = deque()
    fronta.append(v0)

    while fronta:
        u = fronta.popleft()
        print(u, vzdalenost[u])
        for v in graf.sousede(u):
            if not byl_jsem[v]:
                byl_jsem[v] = True
                vzdalenost[v] = vzdalenost[u] + 1
                fronta.append(v)

prohledej(3)