C. Новогодние подарки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Санта-Клаус приготовил коробки с подарками для $$$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 5
1 2 3