Editorial-POTTERCYCLES

First, let’s make sure that all the elements that are out of place form a cycle of odd length.

Suppose there are T cycles in this permutation: [C_{1,1}, \ldots, C_{1,S_1}], \ldots, [C_{T,1}, \ldots, C_{T,S_t}]. Then you can make the spell C_{1,1}, \ldots, C_{1,S_1}, \ldots, C_{T,1}, ..., C_{T,S_T} (here all the cycles are written in a row). After that, inside each cycle, all the elements will be in their places, but the first elements of these cycles will become a new cycle of length T. That is, there will be one cycle of length t, and all other elements will be in their places.

If T is odd, then we have created a cycle of odd length. Otherwise, let’s do the same spell again. Then we will have a cycle of length N-T+1. If this number is odd, then we have made an odd-length cycle. Otherwise, we know that T is even, but N is odd. The resulting permutation (a cycle of even length N-T+1) is odd. Each spell (cycle of odd length N) is an even permutation. And the required permutation (identical) is even. It is impossible to make an odd permutation even by multiplying it by an even permutation, so the answer is `-1`.

Now let the elements A_1, \ldots, A_X be in their places, and all the other elements form a cycle of odd length B_1, \ldots, B_{2Y-1} . Let’s make two spells:

• A_1, \ldots, A_X, B_1, B_{Y+1}, B_2, B_{Y+2}, B_3, B_{Y+3}, \ldots, B_{Y-1}, B_{Y+Y-1}, B_Y
• A_X, \ldots, A_1, B_{Y+1}, B_2, B_{Y+2}, B_3, B_{Y+3}, \ldots, B_{Y-1}, B_{Y+Y-1}, B_Y, B_1

Here, A_i will go to A_{i+1}, and then back to A_i, so they will remain in their places. And B_i will go to B_{(i+Y) \mod (2Y-1)}, and then to B_{(i+Y+Y) \mod (2Y-1)}=B_{(i+1) \mod (2Y-1)}, that is, they will move along the cycle B.