순열에 관한 또 다른 문제

이 문제는 순열에 관한 것이다. 아래에 나오는 용어가 익숙하지 않다면 예제 뒤의 힌트를 참고하라.

순열 $p$의 모든 사이클의 길이가 2 이하이면 $p$를 단순(simple)하다고 한다. 예를 들어 순열 $2, 1, 4, 3$은 단순하지만, 순열 $3, 1, 2$는 단순하지 않다.

순열 $p$가 주어진다. $p$를 최소 개수의 단순한 순열의 곱으로 나타내라.

첫 번째 줄에는 테스트 케이스의 수 $T$가 주어진다 ($1 \le T \le 10^5$).

다음 $T$개의 줄에는 각각 하나의 테스트 케이스가 주어진다. 각 테스트 케이스는 순열 $p$의 길이 $n$ ($1 \le n \le 10^5$)과 $n$개의 서로 다른 정수 $p_1, p_2, \ldots, p_n$으로 이루어진다. 이 정수들은 순열 $p$ 자체이다 ($1 \le p_i \le n$, $1$부터 $n$까지의 각 수가 순열에 정확히 한 번씩 나타난다).

입력에 주어지는 모든 순열의 길이의 합은 $10^6$ 이하이다.

각 테스트 케이스마다, 곱에 들어가는 단순한 순열의 최소 개수 $k$를 한 줄에 출력한다. 그다음 $k$개의 줄에 단순한 순열 $q^{(1)}, q^{(2)}, \ldots, q^{(k)}$를 한 줄에 하나씩 출력한다. 이 중 $i$번째 줄에는 $1$부터 $n$까지의 서로 다른 정수 $n$개로 순열 $q^{(i)}$를 나타낸다. 곱 $q^{(1)} \circ q^{(2)} \circ \ldots \circ q^{(k)}$는 $p$와 같아야 한다.

최적해가 여러 개라면 아무거나 하나를 출력하면 된다.

길이 $n$의 순열은 $1$부터 $n$까지의 각 정수가 정확히 한 번씩 나타나는, 길이 $n$의 정수 수열이다.

순열 $p$의 사이클은 $1$부터 $n$까지의 서로 다른 정수 $i_1, i_2, \ldots, i_t$의 수열로서 $p_{i_1} = i_2$, $p_{i_2} = i_3$, $\ldots$, $p_{i_{t - 1}} = i_t$이고 $p_{i_t} = i_1$을 만족한다. 정수 $t \ge 1$을 그 사이클의 길이라고 한다.

두 순열 $a$와 $b$의 곱 $a \circ b$는 모든 $i$에 대해 $c_i = a_{b_i}$인 순열 $c$이다. 예를 들어 $a = 3 \, 2 \, 1$이고 $b = 1 \, 3 \, 2$이면, 그 곱은 $a \circ b = 3 \, 1 \, 2$이다.

세 개 이상의 순열의 곱은 어떤 순서로 계산해도 결과가 같다. 예를 들어 $a \circ b \circ c = (a \circ b) \circ c = a \circ (b \circ c)$이다.