[USACO08MAR] Pearl Pairing G

题目描述

At Bessie's recent birthday party, she received $N(2 \le N \le 10^5,N\equiv0\pmod{2})$ pearls, each painted one of C different colors ($1\le C \le N$). Upon observing that the number of pearls $N$ is always even, her creative juices flowed and she decided to pair the pearls so that each pair of pearls has two different colors. Knowing that such a set of pairings is always possible for the supplied testcases, help Bessie perform such a pairing. If there are multiple ways of creating a pairing, any solution suffices. 在 Bessie 最近的生日聚会上,她收到 $N(2\le N \le 10^5,N\equiv0\pmod{2})$ 颗珍珠。一共有 $C$ 种颜色的珍珠($1\le C \le N$),第 $i$ 种颜色的珍珠有 $C_i$ 颗。 观察到珍珠的数量 $N$ 总是偶数,她的创意来了,决定配对珍珠,使每对珍珠有两种不同的颜色。数据保证存在答案。请帮助 Bessie 执行这样的配对,如果有多种配对的方法,输出任意一种即可。

输入输出格式

输入格式


Line $1$: Two space-separated integers: $N$ and $C$. Lines $2 \ldots C+1$: Line $i+1$ tells the count of pearls with color $i$: $C_i$. 第 $1$ 行:两个空格分隔的整数:$N$ 和 $C$。 第 $2\ldots C+1$行:第 $i+1$ 为颜色 $i$ 的珍珠数 $C_i$。

输出格式


Lines $1\ldots \dfrac{N}{2}$: Line $i$ contains two integers $a_i$ and $b_i$ indicating that Bessie can pair two pearls with respective colors $a_i$ and $b_i$. 第 $1\ldots \dfrac{N}{2}$ 行:第 $i$ 行包含两个整数 $a_i$ 和 $b_i$,表示 Bessie 可以将各自颜色为 $a_i$ 和 $b_i$ 的两个珍珠配对。

输入输出样例

输入样例 #1

8 3 
2 
2 
4 

输出样例 #1

1 3 
1 3 
2 3 
3 2 

说明

There are $8$ pearls and $3$ different colors. Two pearls have color $\mathrm{I}$; two have color $\mathrm{II}$; four have color $\mathrm{III}$. Bessie pairs each pearl of color $\mathrm{III}$ with one of color $\mathrm{I}$ and $\mathrm{Ii}$. 说明:有 $8$ 颗珍珠和 $3$ 种不同的颜色。两颗珍珠颜色为 $1$,两颗珍珠颜色为 $2$,四颗珍珠颜色为 $3$。 Bessie 将每颗颜色为 $3$ 的珍珠与颜色为 $1$ 和 $2$ 的珍珠配对。 感谢@[线段木](https://www.luogu.com.cn/user/33930) 提供翻译,@[PineappleSummer](https://www.luogu.com.cn/user/880187) 修正翻译以及提供 $\LaTeX$。