CF370C Mittens

在 S 市举办了一场圣诞派对，有 $n$ 个孩子。所有孩子都带着连指手套。手套可能有不同的颜色，但每个孩子的左右手套颜色相同。假设手套的颜色用 $1$ 到 $m$ 的整数编号，孩子则从 $1$ 到 $n$ 编号。则第 $i$ 个孩子的两只手套颜色为 $c_{i}$。 派对上有圣诞老人（在俄语中称为“Father Frost”）、他的孙女雪姑娘，孩子们围着装饰华丽的圣诞树跳舞。事实上，气氛如此明亮多彩，以致于孩子们想让自己左右手的手套颜色不同。孩子们决定交换手套，使得每个人最后得到了一个左手和一个右手的手套，并且这两只手套颜色不同。所有手套都是同一个尺码，适合所有孩子佩戴。 孩子们随意交换手套，结果发现无法让所有人都得到左右手颜色不同的一对手套。Vasily Petrov，是其中一个孩子的爸爸，也是数学家，他发现对于任意情况，让每个孩子都得到一对不同颜色的手套可能并不总是可行。此外，他还设计出一种分配手套的方法，使得能得到不同比色手套的孩子数最大。你的任务是复现他的这个方案。请注意，左手和右手手套是有区别的：每个孩子最后必须得到一只左手手套和一只右手手套。

第一行包含两个整数 $n$ 和 $m$，分别表示孩子的数量和手套可能的颜色种数（$1 \leq n \leq 5000$，$1 \leq m \leq 100$）。第二行包含 $n$ 个整数 $c_{1}, c_{2}, \ldots, c_{n}$，其中 $c_{i}$ 表示第 $i$ 个孩子手套的颜色（$1 \leq c_{i} \leq m$）。

第一行输出可以得到两只手套颜色不同的孩子的最大数量。接下来的 $n$ 行每行输出两个用空格分开的整数，分别表示第 $i$ 个孩子分配到的左手手套和右手手套的颜色。如果有多种方案，输出任意一种即可。

由 ChatGPT 5 翻译