题意简述

有 $n$ 个顶点，第 $i$ 个顶点有权值 $a_i$。依次进行 $x = 1, 2, \dots, n-1$ 次操作：每次操作选择两个尚未被连接（任意状态都可以，只要不形成自环且满足条件）的顶点 $u, v$，要求 $|a_u - a_v|$ 能被 $x$ 整除，然后将它们连边。问能否通过这 $n-1$ 次操作构造出一棵生成树（连通图），若能则输出方案。

解法

存在性：总是存在方案，因为可以在每一步都找到合法的边加入，最终形成一棵树。关键在于算法的构造。

从大到小考虑 $x$（即 $x = n-1, n-2, \dots, 1$）。对于当前 $x$，我们需要找出一对未被加入的顶点 $u, v$ 使得 $|a_u - a_v| \equiv 0 \pmod x$。这等价于 $a_u$ 和 $a_v$ 模 $x$ 同余。利用鸽巢原理，当前未使用的顶点集合大小为 $x+1$（因为已经加入了 $n-1 - x$ 条边，未使用顶点数从 $n$ 递减到 $x+1$）。将这 $x+1$ 个顶点根据模 $x$ 的余数放入 $x$ 个桶中，由鸽巢原理，必有一个桶包含至少两个顶点，这两个顶点模 $x$ 同余，即它们的差被 $x$ 整除。我们可以选择这两个顶点连边。然后将其中一个从未使用集合中移除（因为它已经连入生成树中，另一个保留在集合中继续使用）。

因此，算法为：

• 维护一个“活跃”顶点集合（初始包含所有顶点）。从 $x = n-1$ 到 $1$ 逆序处理：
  • 建立 $x$ 个桶，将活跃顶点按其 $a_i \bmod x$ 放入对应桶。
  • 找到第一个包含至少两个顶点的桶，从中取出两个顶点 $u$ 和 $v$，输出边 $(u,v)$。
  • 从活跃集合中删去 $u$（或 $v$ 之一，保留另一个）。

由于每次都能找到合法边且步骤数正好 $n-1$，最终必然形成连通图（实际上是一棵树，因为每次操作连接两个不同集合，且顶点数逐步减少）。

时间复杂度：每次操作需要遍历活跃集合并建立桶，单次 $O(x+1)$，总复杂度 $O(n^2)$。由于 $\sum n \le 2000$，$O(n^2)$ 完全可行。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int tests;
    cin >> tests;
    while (tests--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto& i : a) cin >> i;
        vector<int> pos(n);
        iota(pos.begin(), pos.end(), 0);
        vector<pair<int, int>> ans;
        for (int i = n - 1; i; --i) {
            vector<int> occ(i, -1);
            for (auto j : pos) {
                if (occ[a[j] % i] != -1) {
                    ans.emplace_back(j, occ[a[j] % i]);
                    pos.erase(find(pos.begin(), pos.end(), j));
                    break;
                }
                occ[a[j] % i] = j;
            }
        }
        reverse(ans.begin(), ans.end());
        cout << "YES\n";
        for (auto [x, y] : ans) cout << x + 1 << ' ' << y + 1 << '\n';
    }
}