Przeszukiwanie grafu wszerz

Limit czasu: 1s | Limit pamięci: 64MB

Napisz program, który wczyta graf skierowany $G = (V, E)$ i znajdzie najkrótszą odległość od wierzchołka $1$ do każdego wierzchołka. Wierzchołki identyfikowane są za pomocą identyfikatorów: $1, 2, \ldots, n$.

Wejście

W pierwszym wierszu podana jest liczba całkowita $n$ oznaczająca liczbę wierzchołków. W kolejnych $n$ wierszach podane są listy sąsiedztwa kolejnych wierchołków podane w następującym formacie:

$u$ $k$ $v_1$ $v_2$ ... $v_k$

$u$ to identyfikator wierzchołka, $k$ oznacza liczbę krawędzi wychodzących z tego wierzchołka, $v_i$ to identyfikatory wierzchołków sąsiadujących z $u$.

Wyjście

Dla każdego wierzchołka wypisz w linii $u$ i $d$.
$u$ to identyfikator wierzchołka, a $d$ to odległość od wierzchołka $1$ do wierzchołka $u$. Jeśli nie ma ścieżki od wierzchołka $1$ do wierzchołka $u$, wypisz $-1$ jako najkrótszą odległość. Kolejne linie wypisz w kolejności rosnących identyfikatorów.

Ograniczenia

• $1 \leq n \leq 100$

Przykłady

Wejście 1

4
1 2 2 4
2 1 4
3 0
4 1 3

Wyjście 1

1 0
2 1
3 2
4 1