Permutation Square Root
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)