The Monkey Dance

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?

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$.

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