Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3996
An Unsure Catch

Time Limit: 6 Seconds      Memory Limit: 65536 KB

Some prisoners have managed to escape from the prison! Your job is to get them back.

At time 0, there are \(n\) prisoners out in the city, each at a different position. We label these positions from 1 to \(n\).

Your colleagues have made a plan to block as many road as possible so that there will be only one way out for each position. Once in an hour, the prisoners at position \(i\) will leave and arrive at position \(a_i\) (\(1 \le a_i \le n\)) immediately.

You can arrange an assault at any integer time at any position. Every prisoner at the same location at that time will be arrested. However, you can only attack once, after that all the prisoners on the run will leave the city.

After consideration, you decide to contact your colleagues to change their plan. Specifically, you can change some \(a_i\) before time 0 (\(1 \le a_i \le n\) must still hold after changing).

Now you want to know, what's the minimum number of \(a_i\) to change (let's denote the answer as \(K\)) in order to catch all the prisoners. You also want to know, if you can change \(a_i\) for at most \(j\) (\(j \in \{0, 1, 2, \dots, K\}\)) times, how many prisoners at most can you arrest. Write a program to solve the problem.

Input

There are multiple test cases. The first line of the input contains an integer \(T\) (\(1 \le T \le 10^4\)), indicating the number of test cases. For each test case:

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), indicating the number of prisoners and positions.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le n\)), their meanings are described above.

For only about 5 cases will \(n\) larger than 50.

Output

For each test case output two lines.

For the first line, print an integer \(K\), indicating the least number of \(a_i\) to change so that you can arrest all the prisoners.

For the second line, print \(K+1\) integers seperated by one space, indicating the number of prisoners you can arrest at most if you can change \(a_i\) for at most \(0, 1, 2, \dots, K\) times.

Please, DO NOT print extra spaces at the end of each line.

Sample Input

2
1
1
10
2 3 1 4 5 7 6 6 6 7

Sample Output

0
1
3
3 6 9 10

Hint

For the second sample test case:

  • If you can change \(a_i\) 0 times, you can change them to: 2 3 1 4 5 7 6 6 6 7. Attacking position 6 at hour 1, and you can arrest 3 prisoners.
  • If you can change \(a_i\) once, you can change them to: 2 3 1 4 5 7 4 6 6 7. Attacking position 4 at hour 3, and you can arrest 6 prisoners.
  • If you can change \(a_i\) twice, you can change them to: 2 3 4 4 5 4 6 6 6 7. Attacking position 4 at hour 3, and you can arrest 9 prisoners.
  • If you can change \(a_i\) 3 times, you can change them to: 2 3 5 5 5 5 6 6 6 7. Attacking position 5 at hour 3, and you can arrest all 10 prisoners.


Author: LIU, Mingrui
Source: ZOJ Monthly, January 2018
Submit    Status