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?
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 I1, I2 means that there is an arrow from circle I1 to circle I2. The input ends with 0 for the value of N.
For each case, simply output the number of steps in the dance. Each output should be on a separate line.
5 1 2 2 3 3 1 4 5 5 4 4 1 4 2 3 4 1 3 2 0
Point Value: 15
Time Limit: 2.00s
Memory Limit: 16M
Added: Apr 18, 2009
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3