Lost Permutation

문제

You once had a permutation $\pi \backslash pi$ of size $nn$. And now it's gone. All you have left is an old device you made while studying group theory. To try and recover $\pi \backslash pi$ you can input a permutation $ff$ of size $nn$ into this device. This device will then display a permutation ${\pi }^{-1}\circ f\circ \pi \backslash pi^\{-1\}\; \backslash circ\; f\; \backslash circ\; \backslash pi$. Find $\pi \backslash pi$ using at most two interactions with the device.

A permutation of size $nn$ is a sequence of $nn$ distinct integers from $11$ to $nn$. The composition of two permutations $aa$ and $bb$ is a permutation $a\circ ba\; \backslash circ\; b$ such that $(a\circ b{)}_i=b_{a_i}(a\; \backslash circ\; b)\_i\; =\; b\_\{a\_i\}$. That is, if we consider a permutation as an action on $nn$ elements, moving element at position $ii$ to $a_{i}a\_i$, then $a\circ ba\; \backslash circ\; b$ is the action that applies $aa$, then applies $bb$, so that element at position $ii$ first moves to $a_{i}a\_i$, then moves to $b_{a_i}b\_\{a\_i\}$. Note that some definitions of composition use the reverse order.

The inverse permutation ${\pi }^{-1}\backslash pi^\{-1\}$ is a permutation $\sigma \backslash sigma$ such that ${\sigma }_{{\pi }_i}=i\backslash sigma\_\{\backslash pi\_i\}\; =\; i$. The composition of a permutation and its inverse is equal to an identity permutation: $(\pi \circ {\pi }^{-1}{)}_i=({\pi }^{-1}\circ \pi {)}_i=i(\backslash pi\; \backslash circ\; \backslash pi^\{-1\})\_i\; =\; (\backslash pi^\{-1\}\; \backslash circ\; \backslash pi)\_i\; =\; i$ for all $ii$ from $11$ to $nn$. For example, if $a=(4,1,3,2)a\; =\; (4,\; 1,\; 3,\; 2)$ and $b=(3,2,1,4)b\; =\; (3,\; 2,\; 1,\; 4)$, then $a\circ b=(4,3,1,2)a\; \backslash circ\; b\; =\; (4,\; 3,\; 1,\; 2)$, $a^{-1}=(2,4,3,1)a^\{-1\}\; =\; (2,\; 4,\; 3,\; 1)$ and $a^{-1}\circ b\circ a=(1,2,4,3)a^\{-1\}\; \backslash circ\; b\; \backslash circ\; a\; =\; (1,\; 2,\; 4,\; 3)$.

힌트

There are two test cases in the first test. In the first test case, $\pi =(4,1,3,2)\backslash pi\; =\; (4,\; 1,\; 3,\; 2)$ is the only permutation that satisfies ${\pi }^{-1}\circ (3,2,1,4)\circ \pi =(1,2,4,3)\backslash pi^\{-1\}\; \backslash circ\; (3,\; 2,\; 1,\; 4)\; \backslash circ\; \backslash pi\; =\; (1,\; 2,\; 4,\; 3)$ and ${\pi }^{-1}\circ (2,4,3,1)\circ \pi =(2,4,3,1)\backslash pi^\{-1\}\; \backslash circ\; (2,\; 4,\; 3,\; 1)\; \backslash circ\; \backslash pi\; =\; (2,\; 4,\; 3,\; 1)$. In the second test case, based on the interaction, $\pi \backslash pi$ can be equal to either $(1,3,2)(1,\; 3,\; 2)$, $(2,1,3)(2,\; 1,\; 3)$, or $(3,2,1)(3,\; 2,\; 1)$. The solution got lucky and guessed the correct one: $(3,2,1)(3,\; 2,\; 1)$.