[Question]
  [
In math, a [permutation](https://en.wikipedia.org/wiki/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***>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
```
  
[Answer]
# Perl, ~~124~~ 122 bytes
Includes +3 for `-alp`
Run with the 1 based permutation on STDIN:
```
rootperm.pl <<< "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)***
[Answer]
# Mathematica, 165 ~~167~~ bytes
An unnamed function.
```
PermutationList[Cycles@Join[Riffle@@@#~(s=Select)~EvenQ@*(l=Length)~SortBy~l~Partition~2,#[[Mod[(#+1)/2Range@#,#,1]&@l@#]]&/@#~s~OddQ@*l]&@@PermutationCycles@#,l@#]&
```
Semi-ungolfed:
```
PermutationList[
    Cycles@Join[
        Riffle@@@Partition[SortBy[Select[#,EvenQ@*Length],Length], 2],
        #[[Mod[(Length@#+1)/2Range@Length@#,Length@#,1]]]& /@ Select[#,OddQ@*Length]
    ]& @@ PermutationCycles @ #,
    Max@#
]&
```
[Answer]
# Prolog - 69 chars
```
p([],_,[]). p([H|T],B,[I|U]):-p(T,B,U),nth1(H,B,I). f(X,Y):-p(Y,Y,X).
```
Explanation:
```
permutate([], _, []).                 % An empty permutation is empty
permutate([X|Xs], List, [Y|Ys]) :-    % To permutate List
  permutate(Xs, List, Ys),            % Apply the rest of the permutation
  nth1(X, List, Y).                   % Y is the Xth element of List
root(Permutation, Root) :-            % The root of Permutation
  permutate(Root, Root, Permutation). % Applied to itself, is Permutation
```
]