Lost Permutation

아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

You once had a permutation π\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 you can input a permutation ff of size nn into this device. This device will then display a permutation π1fπ\pi^{-1} \circ f \circ \pi. Find π\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 aba \circ b such that (ab)_i=b_a_i(a \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_ia\_i, then aba \circ b is the action that applies aa, then applies bb, so that element at position ii first moves to a_ia\_i, then moves to b_a_ib\_{a\_i}. Note that some definitions of composition use the reverse order.

The inverse permutation π1\pi^{-1} is a permutation σ\sigma such that σ_π_i=i\sigma\_{\pi\_i} = i. The composition of a permutation and its inverse is equal to an identity permutation: (ππ1)_i= (π1π)_i=i(\pi \circ \pi^{-1})\_i =  (\pi^{-1} \circ \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 ab=(4,3,1,2)a \circ b = (4, 3, 1, 2), a1=(2,4,3,1)a^{-1} = (2, 4, 3, 1) and a1ba=(1,2,4,3)a^{-1} \circ b \circ a = (1, 2, 4, 3).

힌트

There are two test cases in the first test. In the first test case, π=(4,1,3,2)\pi = (4, 1, 3, 2) is the only permutation that satisfies π1(3,2,1,4)π=(1,2,4,3)\pi^{-1} \circ (3, 2, 1, 4) \circ \pi = (1, 2, 4, 3) and π1(2,4,3,1)π=(2,4,3,1)\pi^{-1} \circ (2, 4, 3, 1) \circ \pi = (2, 4, 3, 1). In the second test case, based on the interaction, π\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).