問題１ - 問題２ - 問題３ - 問題４ - 問題５ - 問題６
NPCA(New Portable Castle Adventure)というゲームがある。
このゲームについて説明する。
・このゲームは、snuke大王にさらわれた hiromu姫を、Mineo が頑張って助けにいくゲームである。
・このゲームは、N 個の面からなり、1 から N までの番号が各面についている。
・Mineo は 1面からスタートし、N面にある城に辿り着いて Tehu大王を倒さなければならない。
・ある面(これを X面とする)をクリアすると次の面(X+1面)に進むことができる。
・N面を除く全ての面には秘密のワープゾーンがあり、1 ~ Nの数字が書かれた「ワープ土管」が M個ある。
・「ワープ土管」に入ると書かれた数字に対応する面に進む(戻る)ことが出来る。
・いずれの「ワープ土管」に書かれている数字も、その「ワープ土管」がある面の番号とは異なる。
太郎君はこのゲームを極めるために、より少ない数の面を経て N面にたどりつく方法を知りたいと思っている。
N面にたどりつくために経なければならない面の数(この値に N面は含めない)の最小値を出力するプログラムを作成せよ。
下図はSample input 1を図示したものである。
「旗」のところにたどりつけばその面はクリアとなり、次の面へ進むことが出来る。
『１面をクリアし、２面で「ワープ土管」に入る』と１面と２面を経るだけで N面にたどりつけるので、2 を出力する。
また、１面で「ワープ土管」に入っても同じ結果になる。
１行目には、面の数 N, 各面にある「ワープ土管」の個数 M 空白を区切りとして書かれている。
1 + i 行目 (1 ≦ i ≦ N-1) には、i 面のワープゾーンにある「ワープ土管」に書かれている数を表す M個の相異なる自然数が空白を区切りとして書かれている。
N面にたどりつくために経なければならない面の数の最小値を出力せよ。
2 ≦ N ≦ 10,000
1 ≦ M ≦ 10
ーSample input 1ー
4 1
2
4
1
ーSample output 1ー
2
ーSample input 2ー
8 2
5 2
1 3
4 5
1 8
4 6
3 7
5 8
ーSample output 2ー
3