from collections import defaultdict

def decompose(p):
    d = dict(enumerate(p))
    ans = defaultdict(list)
    while d:
        x = list(d)[0]
        r = []
        while x in d:
            r.append(x)
            x = d.pop(x)            
        ans[len(r)].append(r)
    return ans

def sqrt(p):
    d = decompose(p)
    n = len(p)
    sqrt_perm = [None for _ in range(n)]
    print(d)
    if any(k % 2 == 0 and len(d[k]) % 2 for k in d.keys()):
        return None
    ans = []
    for key in d.keys():
        xs = d[key]
        if key % 2 == 0:            
            while len(xs) > 1:
                a, b = xs.pop(), xs.pop() 
                c = []
                for i in range(len(a)):
                    c.extend([a[i], b[i]])
                ans.append(c)
        else:
            while len(xs) > 0:
                a = xs.pop()
                k = len(a) // 2
                c = [] 
                for i in range(k):
                    c.extend([a[i], a[i + k + 1]])
                c.append(a[k])
                ans.append(c)

    print(ans)
    for cycle in ans:
        m = len(cycle)
        for i in range(m):
            sqrt_perm[cycle[i]] = cycle[(i + 1) % m]
        
    return sqrt_perm

def sqr(p):
    n = len(p)
    sqr = [None for _ in range(n)]
    for i in range(n):
        sqr[i] = p[p[i]]
    return sqr
p = [0,1,2,3,4]
r = sqrt(p)
print(r)
r2 = sqr(r)
print(r2)
print(sqr([1,7,6,3,2,4,5,0]))