あなたは、とある会社からプログラムの作成を依頼された。 その会社には$N$個の仕事があり、それぞれの仕事には$1$から$N$までの番号が振られている。 仕事$i$には、$M_i$個の前提となる仕事$X_{i,j}$が存在し、仕事$i$を前提となる仕事$X_{i,j}$よりも先に行うと、仕事$i$は多大な損失を被る。
そこであなたには、損失を被る仕事の数が最小となるような順番ですべての仕事を行ったときの損失を被った仕事の数を求めてもらいたい。
入力は以下の形式ですべて整数で与えられる。
$N$ $M_1$ $X_{1,1}$ $X_{1,2}$ ... $X_{1,M_1}$ $M_2$ $X_{2,1}$ $X_{2,2}$ ... $X_{2,M_2}$ : $M_N$ $X_{N,1}$ $X_{N,2}$ ...$X_{N,M_N}$
仕事の数$N$が$1$行に与えられる。
続く$N$行に前提となる仕事の情報が与えられる。$i+1$行目には仕事$i$の情報が空白区切りで与えられる。$M_i$は、仕事$i$の前提となる仕事の数、$X_{i,j}$は仕事$i$の前提となる仕事の番号を表している。
入力は以下の条件を満たす。
損失を被る仕事の数が最小になるような順番ですべての仕事を行ったとき、そのときの損失を被った仕事の数を一行に出力する。
2 1 1 0
1
仕事$1$のように前提となる仕事がその仕事自身となるような入力も存在する。
3 3 2 1 2 0 1 2
1
5 1 2 1 3 2 1 2 3 1 3 5 0
1
例えば、$3,2,1,5,4$の順に仕事を行うと損失を最小化できる。