← 返回题目列表

Codeforces · 370/C

C. 手套

中文机器翻译题面 查看原题

S 市的圣诞晚会有 n 个孩子。所有的孩子都戴着手套。手套的颜色可以不同,但​​每个孩子的左右手套颜色相同。假设手套的颜色用 1 到 m 的整数编号,孩子们的编号从 1 到 n。那么第 i 个孩子的两只手套的颜色都是 ci。

派对上有圣诞老人(俄语中的“霜冻父亲”)和他的孙女雪女,孩子们围着装饰华丽的圣诞树跳舞。事实上,一切都是那么明亮和多样化,孩子们想戴上不同颜色的手套。孩子们决定交换手套,最后每人得到一只左手一只右手一只手套,而且两只手套的颜色不同。所有手套尺寸相同,适合所有儿童。

孩子们开始随意交换手套,但他们无法达到每个孩子都有一双颜色不同的手套的情况。其中一名孩子的父亲瓦西里·彼得罗夫指出,在一般情况下,孩子们的想法可能会被证明是不可能的。此外,他是一位数学家,他想出了这样一个分配手套的方案,让拥有不同颜色手套的孩子数量最多。你的任务是重复他的发现。请注意,左右手套是不同的:每个孩子最终必须拥有一只左手套和一只右手套。

输入

第一行包含两个整数 n 和 m — 孩子的数量和可能的手套颜色数量 (1 ≤ n ≤ 5000, 1 ≤ m ≤ 100)。第二行包含 n 个整数 c1, c2, ... cn,其中 ci 是第 i 个孩子的手套颜色 (1 ≤ ci ≤ m)。

输出

在第一行中,打印最终能获得一双不同颜色手套的儿童的最大数量。在接下来的 n 行中,打印在这种情况下分配手套的方式。在这些行的第 i 行上打印两个以空格分隔的整数:第 i 个孩子将获得的左侧手套的颜色和右侧手套的颜色。如果有多个解决方案,您可以打印其中任何一个。

示例

输入 #1

6 3
1 3 2 2 1 1

输出 #1

6
2 1
1 2
2 1
1 3
1 2
3 1

输入 #2

4 2
1 2 1 1

输出 #2

2
1 2
1 1
2 1
1 1