You once had a permutation π of size n. And now it's gone. All you have left is an old device you made while studying group theory. To try and recover π you can input a permutation f of size n into this device. This device will then display a permutation π−1∘f∘π. Find π using at most two interactions with the device.
A permutation of size n is a sequence of n distinct integers from 1 to n. The composition of two permutations a and b is a permutation a∘b such that (a∘b)_i=b_a_i. That is, if we consider a permutation as an action on n elements, moving element at position i to a_i, then a∘b is the action that applies a, then applies b, so that element at position i first moves to a_i, then moves to b_a_i. Note that some definitions of composition use the reverse order.
The inverse permutation π−1 is a permutation σ such that σ_π_i=i. The composition of a permutation and its inverse is equal to an identity permutation: (π∘π−1)_i= (π−1∘π)_i=i for all i from 1 to n. For example, if a=(4,1,3,2) and b=(3,2,1,4), then a∘b=(4,3,1,2), a−1=(2,4,3,1) and a−1∘b∘a=(1,2,4,3).
There are two test cases in the first test. In the first test case, π=(4,1,3,2) is the only permutation that satisfies π−1∘(3,2,1,4)∘π=(1,2,4,3) and π−1∘(2,4,3,1)∘π=(2,4,3,1). In the second test case, based on the interaction, π can be equal to either (1,3,2), (2,1,3), or (3,2,1). The solution got lucky and guessed the correct one: (3,2,1).