Cycle detection P30452


Statement
 

pdf   zip

html

For any function f that maps a finite set to itself, and for any initial value x0 in the set, the sequence of values x0, x1=f(x0), x2=f(x1), …, xk=f(xk−1), … eventually repeats some values, i.e., there is some i ≥ 0 and some j > i such that f(xj) = f(xi). Once this happens, the sequence continues by repeating the cycle from xi to xj−1.

For instance, the function that maps (0,1,2,3,4,5,6,7,8) to (6,6,0,1,4,3,3,4,0) generates the following sequence when x0 = 2:

2   0   6   3   1   6   3   1   6   3   1   …

In this sequence, the beginning of the cycle (6 3 1) is found after 2 steps. In this case, i=2, j=5, and the periodicity is ji=3.

Given a function that maps the interval [0, n−1] to itself, and several starting values x0, compute the corresponding values of ji and i.

Input

Input starts with the number of cases. Every such case begins with two integer numbers 1 ≤ n ≤ 105 and 0 ≤ k ≤ 10n. Follow, in order, the n images of the numbers in [0, n−1]. Follow k numbers: the x0’s for which the result must be computed.

Output

For every case, print its number and k lines each one with ji and i.

Observation

Since some of the private cases are huge, a recursive program may exhaust the recursion stack.

Public test cases
  • Input

    3
    9 1
    6 6 0 1 4 3 3 4 0
    2
    3 3
    2 1 0
    0 1 2
    4 3
    1 2 3 2
    1 0 1
    

    Output

    Case #1:
     3 2
    Case #2:
     2 0
     1 0
     2 0
    Case #3:
     2 1
     2 2
     2 1
    
  • Information
    Author
    Xavier Martínez
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Setè Concurs de Programacio de la UPC - Final
    Date
    2009-09-16