← 返回题目列表

Codeforces · 1994/D

D. 有趣的游戏

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

Vanya 有一个包含 $$$n$$$ 个顶点的图(编号从 $$$1$$$ 到 $$$n$$$)和一个由 $$$n$$$ 整数组成的数组 $$$a$$$;最初,图中没有边。 Vanya 感到无聊,为了找点乐子,他决定执行 $$$n - 1$$$ 操作。

操作编号$$$x$$$(操作从$$$1$$$开始按顺序编号)如下:

- 选择 $$$2$$$ 不同的数字 $$$1 \leq u,v \leq n$$$,使得 $$$|a_u - a_v|$$$ 可以被 $$$x$$$ 整除。
- 在顶点 $$$u$$$ 和 $$$v$$$ 之间添加一条无向边到图中。

帮助 Vanya 使用 $$$n - 1$$$ 运算获得连通的 $$$^{\text{∗}}$$$ 图,或者确定这是不可能的。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^{3}$$$) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含数字 $$$n$$$ ($$$1 \leq n \leq 2000$$$) — 图中的顶点数。

每个测试用例的第二行包含 $$$n$$$ 数字 $$$a_1, a_2, \cdots a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。

输出

对于每个测试用例,如果没有解决方案,则输出“No”(不带引号)。

否则,输出“Yes”(不带引号),然后输出$$$n - 1$$$行,其中在$$$i$$$行中,输出$$$i$$$运算需要选择的数字$$$u$$$和$$$v$$$。

您可以在任何情况下输出每个字母(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。

示例

输入 #1

8
2
1 4
4
99 7 1 13
5
10 2 31 44 73
5
87 6 81 44 32
5
62 35 33 79 16
5
6 51 31 69 42
5
52 63 25 21 5
12
33 40 3 11 31 43 37 8 50 5 12 22

输出 #1

YES
2 1
YES
4 1
2 1
3 2
YES
5 1
4 1
3 1
2 1
YES
4 1
3 1
2 1
5 4
YES
3 1
5 1
2 1
4 2
YES
4 1
5 1
2 1
3 2
YES
2 1
5 2
3 1
4 3
YES
9 1
12 9
11 1
10 1
6 1
7 6
2 1
8 2
5 2
3 1
4 1

注意

让我们考虑第二个测试用例。

- 第一个操作 $$$(x = 1)$$$:我们可以连接顶点 $$$4$$$ 和 $$$1$$$,因为 $$$|a_4 - a_1| = |13 - 99| =|-86| = 86$$$,并且 $$$86$$$ 可以被 $$$1$$$ 整除。

- 第二个操作 $$$(x = 2)$$$:我们可以连接顶点 $$$2$$$ 和 $$$1$$$,因为 $$$|a_2 - a_1| = |7 - 99| =|-92| = 92$$$,并且 $$$92$$$ 可以被 $$$2$$$ 整除。

- 第三个操作$$$(x = 3)$$$:我们可以连接顶点$$$3$$$和$$$2$$$,因为$$$|a_3 - a_2| = |1 - 7| =|-6| = 6$$$,并且 $$$6$$$ 可以被 $$$3$$$ 整除。