19194번 - Yet Another Problem About Permutations 스페셜 저지다국어

문제

This is a problem about permutations. If you are not familiar with some of the terms used below, please see the note following the example.

A permutation $p$ is said to be simple if the length of each of its cycles does not exceed two. For example, permutation 2,ドル 1, 4, 3$ is simple, but permutation 3,ドル 1, 2$ is not.

You are given a permutation $p$. Your task is to represent it as a product of minimal number of simple permutations.

입력

The first line of input contains one integer $T,ドル the number of test cases (1ドル \le T \le 10^5$). The test cases follow.

Each of next $T$ lines describes a single test case. Each test case description consists of an integer $n,ドル the length of the permutation $p$ (1ドル \le n \le 10^5$), followed by $n$ distinct integers $p_1, p_2, \ldots, p_n,ドル the permutation $p$ itself (1ドル \le p_i \le n,ドル each number from 1ドル$ to $n$ appears in the permutation exactly once).

The total length of all permutations in the input is not greater than 10ドル^6$.

출력

For each test case, start by printing a line containing an integer $k,ドル the minimal number of simple permutations in the product. The next $k$ lines must describe simple permutations $q^{(1)},ドル $q^{(2)},ドル $\ldots,ドル $q^{(k)},ドル one per line. On $i$-th of these lines, print $n$ distinct integers from 1ドル$ to $n$ describing permutation $q^{(i)}$. The product $q^{(1)} \circ q^{(2)} \circ \ldots \circ q^{(k)}$ must be equal to $p$.

If there are several optimal answers, print any one of them.

제한

노트

A permutation of length $n$ is a sequence of $n$ integers where each integer from 1ドル$ to $n$ appears exactly once.

A cycle in a permutation $p$ is a sequence $i_1, i_2, \ldots, i_t$ of distinct integers from 1ドル$ to $n$ such that $p_{i_1} = i_2,ドル $p_{i_2} = i_3,ドル $\ldots,ドル $p_{i_{t - 1}} = i_t$ and $p_{i_t} = i_1$. The number $t \ge 1$ is called the length of the cycle.

The product $a \circ b$ of two permutations $a$ and $b$ is a permutation $c$ such that for each $i,ドル $c_i = a_{b_i}$. For example, if $a = 3 ,円 2 ,円 1$ and $b = 1 ,円 3 ,円 2,ドル their product is $a \circ b = 3 ,円 1 ,円 2$.

The product of three or more permutations can be evaluated in any order, for example, $a \circ b \circ c = (a \circ b) \circ c = a \circ (b \circ c)$.