CF1433D Districts Connection

小镇有 $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$）。

对于每个测试用例，输出： - 如果无法满足题目要求，输出一行 NO。 - 如果可以满足，第一行输出 YES，接下来 $n-1$ 行，每行输出两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n; x_i \ne y_i$），表示第 $i$ 条道路连接的两个区。 对于每条道路 $i$，必须满足 $a[x_i] \ne a[y_i]$。同时，所有区必须连通（可以通过中间区）。

由 ChatGPT 4.1 翻译