CF1090C New Year Presents

圣诞老人已经为 $n$ 个孩子准备好了装有礼物的盒子，每个孩子一个盒子。有 $m$ 种不同的礼物：气球、糖果、巧克力棒、玩具车……每个孩子如果收到两个相同种类的礼物会感到失望，因此每个盒子里的礼物种类都必须各不相同。 在打包完所有礼物后，圣诞老人发现不同的盒子里礼物的数量可能不同。这样对孩子们来说不公平，于是他决定在盒子之间移动一些礼物，使得每个盒子里的礼物数量尽量接近。所有移动完成后，任意盒子中礼物数量的最大值与最小值之差应尽可能小。每个盒子中的礼物种类仍需各不相同。圣诞老人希望尽快完成这项工作，因此他想让所需移动的次数尽量少。 给定每个盒子中礼物的种类，请找出一种最短的移动方案，使得所有盒子中礼物数量的最大值与最小值之差不超过 $1$，并且每个盒子中的礼物种类各不相同。

输入的第一行包含两个整数 $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$，表示最短移动序列的步数，使得所有盒子中礼物数量的最大值与最小值之差不超过 $1$。接下来的 $k$ 行，每行描述一次移动，包含三个整数 $from_i$、$to_i$、$kind_i$，表示将编号为 $from_i$ 的盒子中的 $kind_i$ 号礼物移动到编号为 $to_i$ 的盒子中。盒子的编号按照输入顺序从 $1$ 开始。 在每次移动时，$from_i$ 盒子中必须有 $kind_i$ 号礼物。所有移动完成后，每个盒子中不能有两个相同种类的礼物。 如果有多种最优方案，输出任意一种即可。

由 ChatGPT 4.1 翻译