After shuffling, the $i$-th card from the left is the card a[p[q[i]]]. The trick succeeds if for all $i$ the following equality holds:

Denote by p \circ q the composition of permutations: (p \circ q)[i] = p[q[i]], that is, $q$ is applied first and then $p$. Let $I$ be the identity permutation. Then the condition of the trick can be written as a \circ p \circ q = I.

Apply the inverse permutation a^{-1} to both sides of the equality on the left, and then p^{-1}:

Thus, the permutation $p$ can be chosen arbitrarily, and then $q$ is uniquely determined: q[i] = p^{-1}[a^{-1}[i]]. A permutation without fixed points is called a derangement. The problem reduces to finding a derangement $p$ such that the permutation q = p^{-1} \circ a^{-1} is also a derangement.

Random choice. It is impossible to iterate over all $n!$ permutations $p$, so we choose $p$ at random:

• generate a random permutation $p$; if it has a fixed point, move on to the next attempt;

• compute q = p^{-1} \circ a^{-1};

• if $q$ has no fixed points, the pair $(p,q)$ is the answer.

We make at most $1000$ attempts. If none of them yields an answer, we print "Impossible".

Why it works. An answer does not exist only in a few cases with small $n$:

• n = 1 — there are no permutations without fixed points at all;

• n = 2 and a = (2, 1) — the only derangement p = (2, 1) gives q = (1, 2);

• n = 3 and $a$ swaps exactly two elements. The only derangements of length $3$ are the cyclic shifts (2, 3, 1) and (3, 1, 2). The composition of two cyclic shifts is again a cyclic shift or the identity permutation, so a permutation that swaps two elements cannot be obtained.

For n \ge 4, an answer always exists. Moreover, as an exhaustive search for small $n$ shows, the fraction of suitable permutations $p$ among all $n!$ permutations is at least $1/12$ (the minimum is reached at n = 4), and as $n$ grows it approaches 1/e^2 \approx 0.135. Therefore, the probability of not finding an answer in $1000$ attempts does not exceed (11/12)^{1000} < 10^{-37}, which is practically zero. If no answer exists, none of the attempts will succeed, and the program will correctly print "Impossible".

Example

Consider the fourth test: a = (5, 1, 4, 2, 3).

Let us find the inverse permutation: if a[i] = x, then a^{-1}[x] = i. Since a[1] = 5, a[2] = 1, a[3] = 4, a[4] = 2, a[5] = 3, we get a^{-1} = (2, 4, 5, 3, 1). The figure shows the permutation $a$ on the left and its inverse on the right: all arrows are reversed.

Generate a random permutation $p$ without fixed points. Let, for example, p = (4, 1, 2, 5, 3). Its inverse is p^{-1} = (2, 3, 5, 1, 4).

Compute q[i] = p^{-1}[a^{-1}[i]]:

We get q = (3, 1, 4, 5, 2). The permutation $q$ has no fixed points, so the pair $(p,q)$ is the answer. It coincides with the answer from the example.

Let us check that the trick succeeds, that is, a[p[q[i]]] = i:

In the first test, n = 2 and a = (2, 1), so a^{-1} = (2, 1). The only permutation of length $2$ without fixed points is p = (2, 1), and p^{-1} = (2, 1). Then q = p^{-1} \circ a^{-1} = (1, 2) is the identity permutation, all of whose points are fixed. The answer is "Impossible".

Algorithm implementation

The print function prints the elements of the array $a$, starting from the first one.

void print(vector<int>& a)
{
  for (int i = 1; i < a.size(); i++)
    printf("%d ", a[i]);
  printf("\n");
}

The function is_valid checks whether the permutation $v$ contains any fixed points.

bool is_valid(vector<int>& v)
{
  for (int i = 1; i < v.size(); i++)
    if (v[i] == i) return false;
  return true;
}

Declare the arrays.

vector<int> a, p, p1, q;

The main part of the program. Read the input data.

scanf("%d", &tests);
while (tests--)
{
  scanf("%d", &n);

Initialize the arrays.

  a.resize(n + 1);
  p1.resize(n + 1);
  p.resize(n + 1);
  q.resize(n + 1);

Read the input permutation $a$ and immediately store its inverse in the array $a$. That is, the array $a$ contains the permutation a^{-1}, where $a$ is the input permutation.

  for (i = 1; i <= n; i++)
  {
    scanf("%d", &x);
    a[x] = i;
  }

mt19937 is one of the standard pseudorandom number generators in C++ (Mersenne Twister with a period of 19937). It is very fast and has good statistical properties, making it an excellent choice for most tasks requiring random number generation.

  mt19937 gen(random_device{}());

In the variable $found$, we'll mark whether a solution is found for the current test.

  found = false;

Perform $1000$ iterations.

  for (it = 0; it < 1000; it++)
  {

Generate a random permutation. To do this, populate the array $p$ with the numbers 0, 1, 2, ..., and use the shuffle function to shuffle the elements, starting from the first (non-zero) element. We work with permutations from $1$ to $n$.

    iota(p.begin(), p.end(), 0);
    shuffle(p.begin() + 1, p.end(), gen);

Check whether the permutation $p$ is valid (i.e., it contains no fixed points).

    if (!is_valid(p)) continue;

Compute the permutation p_1 = p^{-1}.

    for (i = 1; i <= n; i++)
      p1[p[i]] = i;

Compute the permutation q = p_1 ° a^{-1} = p^{-1} ° a^{-1}.

    for (i = 1; i <= n; i++)
      q[i] = p1[a[i]];

If the permutation $q$ is valid, print the result.

    if (is_valid(q))
    {
      puts("Possible");
      print(p);
      print(q);
      found = true;
      break;
    }
  }

If no solution is found after $1000$ iterations, then no solution exists.

  if (!found) puts("Impossible");
}