Minimum Transpositions to Equal Rows

You are given a matrix of integers with n rows and m columns. Your task is to determine the minimum number of transpositions required to make all rows equal.

A transposition is defined as the operation where you select a submatrix and transpose it, effectively interchanging its rows and columns. In this problem, the allowed operation is abstracted so that by counting the frequency of identical rows we can compute the answer.

If the matrix already has all rows equal, no transposition is needed and the answer is 0. Otherwise, if there exists at least one row pattern that appears more than once, you can achieve a state where all rows are equal in n − k moves, where k is the maximum frequency of any row. If no row repeats (i.e. maximum frequency is 1), then it is impossible to make all rows equal and the answer is -1.

Note: All formulas are represented in \(\LaTeX\) format. For instance, the minimum number of moves when a row repeated \(k\) times is given by:

\[ \text{moves} = n - k \]

inputFormat

The first line of input contains two integers \(n\) and \(m\), representing the number of rows and columns respectively.

This is followed by \(n\) lines, each containing \(m\) space-separated integers, representing the rows of the matrix.

outputFormat

Output a single integer: the minimum number of transpositions required to make all rows equal. If it is impossible, output -1.

## sample

3 3
1 2 3
3 2 1
1 2 3

1

</p>