## DMOPC '22 Contest 4 P6 - K-Sort

View as PDF

Points: 30 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem types

Kurumi just found a particularly nasty cipher on the internet and she needs your help!

The cipher takes the shape of a permutation of length . According to information she got from the dark web, the solution to the cipher revolves around what is known as a -insert.

Specifically, a -insert of the integer is a two step process:

• Step 1: the integer is removed from .
• Step 2: the integer is inserted after the -th element in the modified . In particular, if , it is inserted at the beginning.

A solution to the cipher is a sequence of -inserts that turns into the identity permutation. In particular, a -insert of the integer is performed as the -th action.

In the interest of time, Kurumi wants to know the shortest possible solution. Can you help Kurumi find the shortest possible ? To ensure the integrity of your solution, there may be up to test cases.

#### Constraints

The array forms a permutation of the integers .

The sum of over all test cases does not exceed .

#### Input Specification

The first line contains an integer , the number of test cases. The remaining lines describe the test cases.

The first line of each test case contains integers, and .

The second line of each test case contains space-separated integers, representing the permutation .

#### Output Specification

For each test case, output two lines.

On the first line, output a single integer , representing the length of .

On the second line, output space-separated integers, representing the solution .

If there are multiple possible solutions, output any one of them.

This problem is graded with a standard checker, so if , you may output an empty line, no line, or a line containing just whitespace.

#### Scoring

For each case within a test, if your output is ill-formatted or your sequence is not a solution, you will receive of the points for that case.

Otherwise, let be the length of the shortest solution.

• If , you will receive of the points for that case.
• If , you will receive of the points for that case.

Your score for a case will be the minimum of the scores of all the tests in the case. Your score for a batch is the minimum of the scores of all of the tests in the batch.

1
4 1
2 3 4 1

2
1 2

#### Explanation for Sample

After the first -insert, the permutation becomes .

After the second -insert, the permutation becomes .

It can be proven that a solution of shorter length does not exist, so this solution would receive of the points for this case.