ChthollyNotaSeniorious получил специальный подарок от AquaMoon: $$$n$$$ бинарных массивов длины $$$m$$$. AquaMoon говорит ему, что за одну операцию он может выбрать любые два массива и любую позицию $$$pos$$$ от $$$1$$$ до $$$m$$$ и поменять местами элементы на позициях $$$pos$$$ в этих массивах.
Его увлекла эта игра, и он хочет найти минимальное количество операций, которые необходимо выполнить, чтобы количество $$$1$$$ во всех массивах было одинаковым. Он пригласил вас принять участие в этой интересной игре, поэтому, пожалуйста, попробуйте найти его!
Если это возможно, пожалуйста, выведите конкретные шаги обмена в формате, описанном в разделе выходных данных. В противном случае, пожалуйста, выведите $$$-1$$$.
Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 2\cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$2 \leq m \leq 10^5$$$).
В $$$i$$$-й из следующих $$$n$$$ строк содержится $$$m$$$ целых чисел $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$$$ $$$(0 \le a_{i, j} \le 1)$$$ — элементы $$$i$$$-го массива.
Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превышает $$$10^6$$$.
Для каждого набора входных данных, если цель недостижима, выведите $$$-1$$$.
В противном случае в первой строке выведите $$$k$$$ $$$(0 \le k \le mn)$$$ — минимальное необходимое количество операций.
$$$i$$$-я из следующих $$$k$$$ строк должна содержать $$$3$$$ целых числа $$$x_i, y_i, z_i$$$ $$$(1 \le x_i, y_i \le n, 1 \le z_i \le m)$$$, которые описывают операцию, которая меняет местами $$$a_{x_i, z_i}, a_{y_i, z_i}$$$: меняет местами $$$z_i$$$-е числа $$$x_i$$$-го и $$$y_i$$$-го массивов.
33 41 1 1 00 0 1 01 0 0 14 31 0 00 1 10 0 10 0 02 20 00 1
1 2 1 1 1 4 2 2 -1
В первом наборе входных данных достаточно выполнить одну операцию: поменять местами первый элемент во второй и первой строках. Массивы станут $$$[0, 1, 1, 0], [1, 0, 1, 0], [1, 0, 0, 1]$$$, каждый из которых содержит ровно две $$$1$$$.
Название |
---|