1999-2000 ACM North Central Regional Programming Contest

Problem 2 — Cycles, Period.

A scientist is making observations (recorded as integer values) of a process that is believed to be cyclic. That is, if the period of the process is p, then the process values observed at times 0, p, 2p, … are all the same, as are those values observed at times 1, p+1, 2p+1, …, and so forth. The scientist also expects that the values that occur in a single cycle are all unique. That is, if the value observed at time t is s_t, then for all i and j such that 0 < i < p, 0 < j < p, we expect that s_i ¹ s_j for i ¹ j.

Unfortunately, the scientist cannot continuously observe the process, so observations are made at somewhat random times. In a log, the scientist records observations as a sequence of pairs of numbers, t and s, where t is the integer elapsed time (since the first observation), and s is the value obtained at that time. The log is maintained in order of increasing time of the observations.

For example, suppose a particular process goes through a cycle with values of 1, 2, 3, 4 and 5. If we assume the first observed value (at time t = 0) is 1, then the scientist’s log might contain the following pairs of integers: (0, 1), (3, 4), (6, 2), (8, 4), (12, 3), (21, 2), (25, 1).

The scientist wants to know if the process is cyclic, and if it is, the period p of the process. Your aid has been enlisted. You are to write a program that uses the data from the log as input, and then reports the cycle period for the process if possible. If no cycle can be determined (either because insufficient data is provided, or the data doesn’t support the existence of a cycle), then an appropriate message is to be displayed.

The period you are to report is the longest that the data supports. For the data to support the assumption that the process is cyclic, the following conditions must hold.

• At least one observed value must occur at least two times. In this case the difference between the times associated with the occurrences must be an integer multiple of the cycle period.
• The difference between the times associated with repeated occurrences of the same data value must be a multiple of the cycle period.

If no observed process values are repeated in the log, then you are to assume the process is not cyclic and report that fact.

Input

The input data will contain multiple test cases. Each test case will consist of an arbitrary number of observations reported as pairs of integers, each pair containing the time of observation and the process value. Process values will always be greater than zero. The input for each test case will be terminated with a pair of zeroes, which are not to be treated as data. An additional pair of zeroes will follow the last test case, effectively representing a test case with no observations, which is not to be processed.

Output

For each test case, determine if the given log data indicates the process is cyclic. If so, report the longest possible period supported by the data in a form similar to that shown below. If the log data does not support identification of the process as cyclic, then report that fact, again in a form similar to that shown below.

Sample Input

0 1 3 4 6 2 8 4 12 3 21 2 25 1 0 0

0 1 10 1 20 1 0 0

0 1 10 2 0 0

0 0

Expected Output

Case 1: cycle time = 5.

Case 2: cycle time = 10.

Case 3: no cycle time can be determined.