405593: GYM102006 F Pretests

In a contest like the one you are participating in currently, a verdict of Accepted means that your solution was run on all test cases and produced the correct output for them all. However, some popular websites that hold online rounds prefer to use a pretest system. Your solution would be run on a subset of the test cases when you submit it, otherwise known as pretests.

For a problem with t pretests, solutions are judged on them in order, one by one, until it fails to produce a correct output. So, if a solution fails on the k^th test, it will request k test runs, and if it never fails, it will request t test runs.

To prevent the system from lagging, it would be preferable if the total number of test runs for all submissions was minimized.

You are given the verdicts of n submissions on each of the t pretest cases.

Print the minimum total number of runs needed if the pretests were ordered optimally. If there is more than one order that minimizes the answer, print the lexographically smallest one.

The first line of input contains a single integer P, the number of problems you are ordering the pretests for.

The first line for each of the P problems contains two space-separated integers t and n (1 ≤ t ≤ 20) (1 ≤ n ≤ 2 × 10⁵), the number of pretests for this problem and the number of submissions, respectively.

Each of the following n lines contains t characters representing the verdicts of this submission on each of the pretests, the i^th character is '1' if this submission passes the i^th pretest, or '0' if it fails.

For each of the P problems, output two lines. On the first line, print the minimum total number of test runs needed if the pretests were ordered optimally.

On the second line, print a permutation of the numbers from 1 to t, representing the lexographically smallest order of the pretests that produces the minimum answer.

1
4 3
1100
0101
0011

4
1 3 2 4

A permutation a is lexicographically smaller than permutation b if there exists an index i such than a_i < b_i and a_j = b_j for all (1 ≤ j < i).