luogu#P8103. 「LCOI2022」 Cow Merger

「LCOI2022」 Cow Merger

题目背景

Bessie 来到她的新家之后,Farmer John 突然意识到自己农场的大小不够了!

所以,Farmer John 需要把所有的奶牛合并到一个牛棚里。

题目描述

Farmer John 的农场里本来有 nn 个牛棚,第 ii 个牛棚里住着 aia_i 只牛。

我们定义一次合并 i,j(aiaj)i,j(a_i\ge a_j) 两个牛棚的操作为:从 ii 号牛棚中拿出 aja_j 头牛,放入 jj 号牛棚中。如果在合并结束后 ai=0a_i=0,那么可以看做 aia_i 被合并了,接下来的操作也与 aia_i 无关。

由于时间不够了,他决定最多你 11 秒的时间。

输入格式

第一行包含一个整数 TT,表示数据组数。

对于第 tt 组数据:

2t2t 行包含一个整数 nn

2t+12t+1 行包含 nn 个整数,第 ii 个整数为 aia_i

输出格式

对于每组数据:

如果你发现自己不可能达到目标,输出 NO,否则输出 YES

接下来一行,输出一个整数 mm 表示操作次数。

接下来 mm 行,每行输出两个数 iijj(注意操作时应满足 aiaja_i \ge a_j)。

有多解时可输出任意一组解。

3
4
1 2 3 2
5
3 9 6 18 12
5
2 3 5 7 11
YES
4
3 1
1 2
3 4
2 4
YES
6
2 1
1 2
4 3
2 3
4 5
3 5
NO

提示

【数据范围与约定】

对于 100%100\% 的数据,1T51 \leq T \leq 51n1051 \leq n \leq 10^50ai1090 \leq a_i \leq 10^9