### Problem A

## The Monkey Dance

**Input file:** a.in

**Output file:** a.out

**Source file:** n:\a\a.{c, cpp, pas}
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

The input may have multiple cases.
Each case consists of the value of *N* (1 <= *N* <= 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

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