Permutation Square Root In math, a permutation σ of order n is a bijective function from the integers 1...n to itself. This list:
2 1 4 3

represents the permutation σ such that σ(1) = 2, σ(2) = 1, σ(3) = 4, and σ(4) = 3.
A square root of a permutation σ is a permutation that, when applied to itself, gives σ. For example, 2 1 4 3 has the square root τ =3 4 2 1.
k           1 2 3 4
τ(k)        3 4 2 1
τ(τ(k))     2 1 4 3

because τ(τ(k)) = σ(k) for all 1≤k≤n.
Input
A list of n&gt;0 integers, all between 1 and n inclusive, representing a permutation. The permutation will always have a square root.
You may use a list of 0...n-1 instead as long as your input and output are consistent.
Output
The permutation's square root, also as an array.
Restrictions
Your algorithm must run in polynomial time in n. That means you can't just loop through all n! permutations of order n.
Any builtins are permitted.
Test cases:
Note that many inputs have multiple possible outputs.
2 1 4 3
3 4 2 1

1
1

3 1 2
2 3 1

8 3 9 1 5 4 10 13 2 12 6 11 7
12 9 2 10 5 7 4 11 3 1 13 8 6

13 7 12 8 10 2 3 11 1 4 5 6 9
9 8 5 2 12 4 11 7 13 6 3 10 1
Perl, 124 122 bytes

Includes +3 for -alp

Run with the 1 based permutation on STDIN:

rootperm.pl &lt;&lt;&lt; "8 3 9 1 5 4 10 13 2 12 6 11 7"


rootperm.pl:

map{//;@{$G[-1]^$_|$0{$_}}{0,@G}=(@G=map{($n+=$s{$_=$F[$_-1]}++)?():$_}(0+$',0+$_)x@F)x2,%s=$n=0for@F}@F;$_="@0{1..@F}"


Complexity is O(n^3)