← 返回题目列表

Codeforces · 1579/D

D. 富有成效的会议

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

即将召开一个重要会议,邀请了 $$$n$$$ 人。任何时候,任何两个人都可以退后一步,私下交谈。同一两个人每次会议可以交谈多次(只要他们愿意)。

每个人的社交能力都是有限的。第 $$$i$$$ 人的社交能力是一个非负整数 $$$a_i$$$。这意味着在 $$$a_i$$$ 讲话之后,此人离开会议(并且不再与其他任何人交谈)。如果 $$$a_i = 0$$$,则第 $$$i$$$ 人在会议开始后立即离开会议。

如果会议期间进行了尽可能多的会谈,则会议被认为是最富有成效的。

给你一组社交能力$$$a$$$,确定哪些人应该互相交谈,以使交谈的总数尽可能多。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

接下来的 $$$2t$$$ 行包含测试用例的描述。

每个测试用例描述的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) - 会议中的人数。第二行由 $$$n$$$ 空格分隔的整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2 \cdot 10^5$$$) 组成 - 所有人的社交参数。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。还保证所有$$$a_i$$$(所有测试用例和所有$$$i$$$)的总和不超过$$$2 \cdot 10^5$$$。

输出

打印所有测试用例的 $$$t$$$ 答案。

在每个答案的第一行打印数字 $$$k$$$ — 会议中可能的最大演讲数量。

在接下来的 $$$k$$$ 行中,打印两个整数 $$$i$$$ 和 $$$j$$$ ($$$1 \le i, j \le n$$$ 和 $$$i \neq j$$$) - 将进行另一次演讲的人数。

如果有多个可能的答案,您可以打印其中任何一个。

示例

输入 #1

8
2
2 3
3
1 2 3
4
1 2 3 4
3
0 0 2
2
6 2
3
0 0 2
5
8 2 0 1 1
5
0 1 0 0 6

输出 #1

2
1 2
1 2
3
1 3
2 3
2 3
5
1 3
2 4
2 4
3 4
3 4
0
2
1 2
1 2
0
4
1 2
1 5
1 4
1 2
1
5 2