镇上有$$$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