Canadian Computing Competition: 2001 Stage 2, Day 1, Problem 1

The director of Hind Circus has decided to add a new performance, the monkey dance, to his show. The monkey dance is performed simultaneously by ~N~ monkeys. There are ~N~ circles drawn on the ground, labelled from ~1~ to ~N~. In the beginning, each monkey sits on a different circle. There are ~N~ arrows drawn from circle to circle in such a way that there is exactly one arrow pointing toward each ring and exactly one arrow pointing away from each ring.

When the show begins, at each whistle of the ringmaster, all the monkeys simultaneously jump from their respective circles to other circles following the arrows from their respective current circles. This is one step of the dance. The dance ends when all the monkeys have returned to the circles where they initially started. How long does the dance last?

Input Specification

The input may have multiple cases. Each case consists of the value of ~N~ ~(1 \le N \le 100)~ on a line, followed by ~N~ lines, each with a pair of integers between ~1~ and ~N~. The pair ~I_1~, ~I_2~ means that there is an arrow from circle ~I_1~ to circle ~I_2~. The input ends with 0 for the value of ~N~.

Output Specification

For each case, simply output the number of steps in the dance. Each output should be on a separate line.

Sample Input

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

Sample Output

6
2