Time Limit: 2 second(s) | Memory Limit: 32 MB |
N students are standing in a line. They are wearing colored t-shirts. For simplicity, let's assume that the color of each person is an integer between 1 and 16. Like color 1 represents red, color 2 represents blue, and so on.
Now the students with same colored t-shirts want to join together. So, they are thinking what to do. That's why you are here to the rescue! You have to solve this problem. You have to say the minimum number of swaps necessary to reformat the line such that the people with same colored t-shirt come together. A swap means changing position between two adjacent people in the line.
Input starts with an integer T (≤ 15), denoting the number of test cases.
Each case starts with two integers N (1 ≤ N ≤ 10^{5}) and m (1 ≤ m ≤ 16), where m denotes the number of total colors. So, the students in the line will have a t-shirt color between 1 and m. The next line contains N space separated integers. Each of these integers will lie between 1 and m, denoting the color of the i^{th} person in the line.
For each case, print the case number and the minimum number of swaps necessary to arrange them according to the description.
Sample Input |
Output for Sample Input |
3 4 2 1 2 1 2 6 4 2 1 4 3 1 2 8 6 1 3 2 5 5 4 5 2 |
Case 1: 1 Case 2: 6 Case 3: 5 |
Dataset is huge. Use faster i/o methods.
Developed and Maintained by
JANE ALAM JAN |
Copyright © 2012
LightOJ, Jane Alam Jan |