def gcd(a,b):
    """Return the greatest common divisor using Euclid's Algorithm."""
    while b:     
        a, b = b, a % b
    return a
 
def lcm(a,b):
    return a*(b/gcd(a,b))
 
def cycle_decomposition(p):
    n = len(p)
    cycles = 1
    for i in range(n):
        if p[i]>=0: # if this item has not been visited
            length = 0 # length of current cycle starting with i
            j = i # j is the moving index in the cycle starting with i
            while j!=i or length==0:           
                tmp = j
                length += 1
                j = p[j]
                p[tmp] = -1  # indicate that this item has been visited
            #print length
            cycles = lcm(cycles,length) #
            print cycles
    return cycles