P5036 随机生成树

@葛军 改编的水题。

rainheavy 在纸上画了 $N$ 个点（从 $1$ 到 $N$ 编号），每个点的颜色用一个整数描述。rainheavy 决定用这 $N$ 个点随机生成一棵树，生成的规则如下： 对于 $2$ 号点到 $N$ 号点，每个点随机指定连接一个点。$i$ 号点 $(2 \le i \le N)$ 连的点在 $i$ 的约数中和 $i$ 的倍数中不超过 $N$ 的中随机挑选一个。（例如 $N=30$ 时 $10$ 号点的可以连接 $1$ 号，$2$ 号，$5$ 号，$20$ 号，$30$ 号） 生成的树中不能有重边。（不然就不叫树了） 树生成完之后，rainheavy 可以计算出这个树有多少个联通块，一个联通块是一些点的集合，需要满足以下两个条件： 1、从集合中任取两个点都满足：两个点颜色相同，且这两个点之间存在一条树边组成的路径，路径上的所有点都和这两个点颜色相同。 2、对于集合中的任意一个点和集合外的任意一个点：两点要么不同色，要么不存在一条树边组成的路径使得路径上所有点都和这两个点同色。 rainheavy 希望计算出生成的树中联通块个数最多时，需要连接哪些边，但是 rainheavy 太强了，不屑于做这种辣鸡题目，~~更重要的是他要去 AK IOI~~，于是就把题目扔给了你。 注：边的顺序 1. 首先，满足连通块个数最多的优先（即对于生成连通块有贡献的优先）。 2. 同样满足条件 $1$ 时，连接的两个点编号之和较小的边优先。（如满足条件 $1$ 时，连接 $3$ 号点和 $5$ 号点的边比连接 $4$ 号点和 $5$ 号点的边优先） 3. 同时满足条件 $2$ 时，连接的两个点编号的之中较小的一个较小的边优先。（如满足条件2时，连接2号点和6号点的边比连接3号点和5号点的边优先）

第一行一个整数 $N$ 代表点数。 第二行 $N$ 个整数，第 $i$ 个整数 $c_i$ 代表第 $i$ 个点的颜色。

输出共 $N-1$ 行，每行两个整数 $x,y$ 表示需要一条边连接点 $x$ 和点 $y$。（要求 $x

对于样例的解释：因为 $2$ 号、$4$ 号点会对生成联通块有贡献（$3$ 号你连了也没用），又因为 $1+2 \lt 1+4$ ，所以 $(1,2)$ 比 $(1,4)$ 优先输出，最后再输出 $(1,3)$。 对于 $30\%$ 的数据，$2 \le N \le 10$； 对于 $60\%$ 的数据，$2 \le N \le 5000$； 对于 $80\%$ 的数据，$2 \le N \le 2 \times 10^5$； 对于 $100\%$ 的数据，$2 \le N \le 5 \times 10^5,1 \le c_i \le 10^9$。（反正多了也没用）