The Monkey Dance

Interview

Time limit1sMemory limit128 MB

Summary

Each monkey follows one outgoing arrow per step on a permutation; find the step count when all monkeys are back home, which is the LCM of the cycle lengths.

Level: Medium4 of 10
Topics: Graph, Math, Simulation, Number theory
Solved: No attempts yet

Problem

The director of Hind Circus has decided to add a new act, the monkey dance, to the show. The monkey dance is performed by $N$ monkeys at the same time. On the ground there are $N$ circles labelled from $1$ to $N$ , and at the start each monkey sits on a different circle. There are $N$ arrows drawn between the circles so that exactly one arrow leaves each circle and exactly one arrow enters each circle.

Once the show starts, every time the ringmaster blows the whistle all monkeys simultaneously jump from their current circle to another circle by following the arrow that leaves their current circle. This is one step of the dance. The dance ends when every monkey has returned to the circle where it started. How many steps does the dance last?

Input

The input may contain several test cases. Each case begins with a line holding the number of circles $N$ $(1 \le N \le 100)$ , followed by $N$ lines that each contain a pair of integers between $1$ and $N$ . The pair $I_1$ , $I_2$ means there is an arrow from circle $I_1$ to circle $I_2$ . The input ends with a line whose value of $N$ is $0$ .

Output

For each test case, print the number of steps in the dance, one value per line.

Examples6

Example 1

Input

Expected output

6
2

Example 2
Input
```
1
1 1
0
```
Expected output
```
1
```
Example 3
Input
```
4
1 1
2 2
3 3
4 4
0
```
Expected output
```
1
```
Example 4
Input
```
5
1 2
2 3
3 4
4 5
5 1
0
```
Expected output
```
5
```

Example 5

Input

Expected output

3
4

Example 6

Input

Expected output