幅優先探索

与えられた有向グラフ $G = (V, E)$ について、頂点 $1$ から各頂点への最短距離 $d$（パス上の辺の数の最小値）を求めるプログラムを作成してください。各頂点には $1$ から $n$ までの番号がふられているものとします。頂点 $1$ からたどり着けない頂点については、距離として-1 を出力してください。

入力

最初の行に $G$ の頂点数 $n$ が与えられます。続く $n$ 行で各頂点 $u$ の隣接リストが以下の形式で与えられます：

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

$u$ は頂点の番号、$k$ は $u$ の出次数、$v_1\; v_2\; ...\; v_k$　は $u$ に隣接する頂点の番号を示します。

制約

• $1 \leq n \leq 100$

出力

各頂点について $id$、$d$ を１行に出力してください。$id$ は頂点の番号、$d$ は頂点 $1$ からその頂点までの距離を示します。頂点番号順に出力してください。

入力例 1

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

出力例 1

1 0
2 1
3 2
4 1

参考文献

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

---