2001 Canadian Computing Competition, Stage 2

Day 1, Problem 1: The Monkey Dance

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₁, I₂ means that there is an arrow from circle I₁ to circle I₂. 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

All Submissions
Best Solutions

Point Value: 15
Time Limit: 2.00s
Memory Limit: 16M
Added: Apr 18, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

All of the test input (found at official cemc site) work on my computer, even test case 5.
I found that I had to copy the test data (except for the first one) into word or the formatting would be all weird. Also, the weirdly formatted ones seemed to be terminated with a right pointing 'arrow' character. Would this be the reason for the runtime errors?

Perhaps this works differently on your compiler...
But on my computer, and on the Judge, if you have
cin >> a >> b;
When your program inputs b, it doesn't yet have the value of a. Always safer to do
cin >> a;
cin >> b;

Thanks, that solved it.
The code worked fine on my computer, but I guess I'll keep that in mind for future solutions.

You may need to use a long long (C++) or an int64 (PAS) to compute your answer.

Although it is not absolutely necessary; SourSpinach's code avoids it. I do believe the maximum possible answer is 223092870, which fits in an int/longint.

A naive approach (that is, just simulating each round) will [i]not[/i] work in time.