Задача №114479. Новогодние подарки
Санта-Клаус приготовил коробки с подарками для \(n\) детей, по одной коробке каждому ребёнку. В коробках есть \(m\) видов подарков: воздушные шары, конфеты, шоколадки, игрушечные машинки... Любой ребёнок расстроится, получив два одинаковых подарка, поэтому все подарки в каждой коробке различны.
Только упаковав все коробки, Санта заметил, что в разных коробках разное число подарков. Это несправедливо по отношению к детям! Санта решил переместить некоторые подарки из одной коробки в другую, чтобы в итоге размеры самой большой и самой маленькой коробки отличались как можно меньше. Все подарки в каждой коробке по-прежнему должны оказаться различными. Санта хочет расправиться с работой побыстрее, поэтому ему нужно минимизировать число перемещений.
Вам даны списки подарков в каждой коробке. Найдите кратчайшую последовательность перемещений подарков между коробками, в результате которой размеры самой большой и самой маленькой коробки будут отличаться как можно меньше, и все подарки в каждой коробке будут различны.
В первой строке содержатся два целых числа \(n\) и \(m\) (\(1 \leq n, m \leq 100\ 000\)) — количество коробок и видов подарков. Будем обозначать виды подарков целыми числами от \(1\) до \(m\).
Каждая из следующих \(n\) строк содержит описание коробки. Описание начинается с целого числа \(s_i\) (\(s_i \geq 0\)) — количества подарков в коробке. Затем идут \(s_i\) различных чисел между \(1\) и \(m\) — виды подарков в данной коробке.
Суммарное количество подарков во всех коробках не превосходит \(500\,000\).
В первой строке выведите одно число \(k\) — минимальное число перемещений подарков между коробками, которое позволяет Санте добиться желаемого. Затем выведите \(k\) строк с описаниями перемещений. Перемещения должны быть выведены в том же порядке, в котором их требуется применить. Каждое перемещение описывается тремя числами \(from_i\), \(to_i\), \(kind_i\). Это значит, что подарок вида \(kind_i\) перемещается из коробки с номером \(from_i\) в коробку с номером \(to_i\). Коробки нумеруются с единицы в порядке следования во входных данных.
Перед перемещением хотя бы один подарок вида \(kind_i\) должен находиться в коробке с номером \(from_i\). После окончания всех перемещений ни в какой коробке не должно находиться двух подарков одного вида.
Если оптимальных последовательностей перемещений несколько, выведите любую из них.
3 5 5 1 2 3 4 5 2 1 2 2 3 4
2 1 3 1 1 2 3