Tag Discussion Solution Statistics Submit
 

KUPC (Fuka Cup 3)

Let's JUMPSTYLE

Time Limit : 8 sec, Memory Limit : 65536 KB

Problem B: Let's JUMPSTYLE

Description

踊りの好きなFは,とあるダンスホールでJUMPSTYLEと呼ばれるハードコアな踊りの練習をすることにした.

フロアはN×Nの格子状にタイルが敷き詰められている. 踊りの練習をサポートするため,各タイルには次のステップに飛び移るべきタイルの座標が書かれている.Fは日々の練習によって強靭な運動神経を持っており,フロア内の任意のタイルへ飛び移ることができる.

Fは,十分に長い時間この踊りを続けていけば,いつか定常状態に入り,同じルートをただループする状態になることに気付いた.Fはこのようなループがこのフロアにいくつ存在するのか疑問に思い,プログラマであるあなたに相談することにした.

Input

入力は複数のテストケースから成る.

各テストケースはフロアの1辺の長さNを含む1行で始まる.(1 ≦ N ≦ 100)

続くN行は,フロアの各タイルに書いてあるジャンプ先の座標を以下のように表している.


\begin{array}{ccccccc}
 x_{0,0} & y_{0,0} & x_{1,0} & y_{1,0} & \cdots & x_{N-1,0} & y_{N-1,0} \\
 x_{0,1} & y_{0,1} & x_{1,1} & y_{1,1} & \cdots & x_{N-1,1} & y_{N-1,1} \\
 \vdots  & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
 x_{0,N-1} & y_{0,N-1} & x_{1,N-1} & y_{1,N-1} & \cdots & x_{N-1,N-1} & y_{N-1,N-1} 
\end{array}

x_{i,j},\  y_{i,j} は,それぞれ座標(i, j)にあるタイルに書いてあるジャンプ先のx座標およびy座標を表す.座標は0-originであり,すべての座標の値は0以上N未満の整数である.

入力は0のみから成る行で終わる.

Output

各テストケースに対し,異なるループの個数を1行で出力する.

Sample Input

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

Output for Sample Input

1
2
1
2
3

Source: Kyoto University Micro Computer Club , Fuka Cup 3, Kyoto, Japan