← 返回题目列表

Codeforces · 1433/D

D. 地区连接

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

镇上有$$$n$$$个区,第$$$i$$$区属于第$$$a_i$$$个土匪团伙。最初,没有任何地区相互连接。

你是该市的市长,想要修建 $$$n-1$$$ 双向道路来连接所有区(两个区可以直接连接,也可以通过其他连接的区连接)。

如果属于同一帮派的两个地区直接有道路相连,该帮派就会叛乱。

你不希望这样,所以你的任务是建造 $$$n-1$$$ 双向道路,使得所有地区都可以相互到达(可能使用中间地区),并且每对直接连接的地区属于不同的帮派,或者确定不可能建造 $$$n-1$$$ 道路来满足所有条件。

您必须回答 $$$t$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 5000$$$) — 区数。测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 区所属的帮派。

保证 $$$n$$$ 的总和不超过 $$$5000$$$ ($$$\sum n \le 5000$$$)。

输出

对于每个测试用例,打印:

- 如果无法连接满足问题陈述中的条件的所有区域,则在唯一的线路上为“否”。
- 第一行是 YES,接下来的 $$$n-1$$$ 行是 $$$n-1$$$ 道路。每条道路应表示为一对整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n; x_i \ne y_i$$$),其中 $$$x_i$$$ 和 $$$y_i$$$ 是第 $$$i$$$ 条道路连接的两个区。

对于每条道路 $$$i$$$,应满足条件 $$$a[x_i] \ne a[y_i]$$$。此外,所有区域应该可以相互访问(可能使用中间区域)。

示例

输入 #1

4
5
1 2 2 1 3
3
1 1 1
4
1 1000 101 1000
4
1 2 3 4

输出 #1

YES
1 3
3 5
5 4
1 2
NO
YES
1 2
2 3
3 4
YES
1 2
1 3
1 4