Strange Matrix
Contest: Kotlin Heroes: Episode 11
Tags: *special, graphs, greedy

You are given a matrix $$$a$$$ of size $$$n \times m$$$, consisting of integers from $$$0$$$ to $$$31$$$ inclusive.

Let's call the matrix strange if for every two distinct rows $$$i$$$ and $$$j$$$, both of the following conditions hold:

- for every set of $$$k$$$ indices $$$(x_1, x_2, \dots, x_k)$$$, where $$$1 \le x_1 < x_2 < \cdots < x_k \le m$$$, the equality $$$a_{i, x_1} \mathbin{\&} a_{j, x_1} \mathbin{\&} a_{i, x_2} \mathbin{\&} a_{j, x_2} \mathbin{\&} \cdots \mathbin{\&} a_{i, x_k} \mathbin{\&} a_{j, x_k} = 0$$$ holds (where $$$\mathbin{\&}$$$ — bitwise AND of two numbers);
- for every set of $$$k$$$ indices $$$(x_1, x_2, \dots, x_k)$$$, where $$$1 \le x_1 < x_2 < \cdots < x_k \le m$$$, the equality $$$a_{i, x_1} \mathbin{|} a_{j, x_1} \mathbin{|} a_{i, x_2} \mathbin{|} a_{j, x_2} \mathbin{|} \cdots \mathbin{|} a_{i, x_k} \mathbin{|} a_{j, x_k} = 31$$$ holds (where $$$\mathbin{|}$$$ — bitwise OR of two numbers).

You can perform the following operation any number of times: take any row of the matrix and a number $$$y$$$ from $$$0$$$ to $$$31$$$ inclusive; then apply the bitwise XOR with the number $$$y$$$ to all elements of the selected row. The cost of such an operation is equal to $$$y$$$.

Your task is to calculate the minimum cost to make the matrix strange, or report that it is impossible.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n, m \le 50$$$; $$$1 \le k \le m$$$).

Next, there are $$$n$$$ lines, the $$$i$$$-th of which contains $$$m$$$ integers $$$a_{i, 1}, a_{i, 2}, \dots, a_{i, m}$$$ ($$$0 \le a_{i, j} \le 31$$$).

Output format:
For each test case, output one integer — the minimum cost to make the matrix strange, or -1 if it is impossible to make the matrix strange.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
3
2 3 1
0 1 0
1 0 1
3 2 2
0 1
2 3
4 5
5 5 5
0 5 17 4 22
8 5 16 21 9
7 25 31 30 8
0 0 5 15 13
1 2 3 4 5

Example output:
30
-1
24

Editorial:
Note that the problem can be solved bit by bit. It remains to determine for each row whether XOR needs to be performed or not.
Consider two rows of the matrix and the definition of a strange matrix for them. The first condition means that there are no $$$k$$$ indices where this bit is $$$1$$$ in both rows. The second condition means that there are no $$$k$$$ indices where this bit is $$$0$$$ in both rows.
Notice that if we apply XOR to both rows, that doesn't affect the fulfillment of the strangeness conditions. Also, note that applying XOR only to the first row is equivalent (in terms of their "strangeness") to applying XOR only to the second row.
Thus, for each pair of rows, there are $$$4$$$ possible situations:
1. XOR can be applied in any way;
2. XOR needs to be applied only to one;
3. XOR needs to be applied to both or not applied at all;
4. the "strangeness" condition is never fulfilled.
If there is a pair of rows for which the last situation occurs, then the answer to the problem is $$$-1$$$.
Each pair of rows is constrained by conditions $$$2$$$ and $$$3$$$. They must be either in different groups (regarding the need to XOR) or in the same group.
This brings us to the bipartite coloring problem. Let's create a graph with $$$n$$$ vertices, connecting pairs of type $$$2$$$ with edges of length $$$1$$$, and pairs of type $$$3$$$ with edges of length $$$0$$$. It remains to check that each connected component is bipartite (if it is not, then the answer to the problem is $$$-1$$$). After coloring the components, we must choose the color with fewer vertices and XOR all given rows.