Maximizing Connected Blocks in a Divisor‐Multiple Tree

Given a set of N points numbered from 1 to N, each with an integer color, we want to build a spanning tree using a special rule and then output the chosen edges in a specific order. The available edges are defined as follows:

For any two distinct points u and v, an edge (u,v) is available if and only if, when we assume u < v, u divides v (i.e. \( u|v \)). (This rule is equivalent to saying that for any point i (2 ≤ i ≤ N), its candidate connecting points are those j (j ≠ i) satisfying that either \(j|i\) or \(i|j\), with the additional natural bound that all indices lie between 1 and N.)

The tree is generated by selecting exactly N-1 edges such that the final graph is connected and acyclic. However, the twist is that we want to maximize the number of connected blocks. A connected block is defined as a maximal set of vertices such that:

1. Any two vertices in the set have the same color and there is a path between them using tree edges with every vertex on that path having that same color.
2. For any vertex in the block and any vertex not in the block, either their colors are different or no path exists that is entirely composed of vertices of that same color.

If no edge that connects points of the same color is used, then every vertex is its own block. Thus, to maximize the number of connected blocks, we want as many edges as possible to connect points of different colors. In other words, if we assign a weight of \(1\) to an edge connecting two vertices of different colors and \(0\) to an edge connecting vertices of the same color, then our goal is to choose a spanning tree with maximum total weight.

After constructing such a spanning tree, the output edges must be sorted with the following priorities:

1. All edges that connect vertices of different colors (i.e. contribute to the maximum block count) come first.
2. Within each group (different‐colored or same‐colored), the edge whose endpoints’ sum is smaller comes first. (If we have two edges \((u,v)\) and \((x,y)\), compare \(u+v\) with \(x+y\)).
3. If there is still a tie, the edge with the smaller minimum vertex appears first.

You are to output the list of edges (each edge contains two endpoints, printed with the smaller number first) of the spanning tree that maximizes the number of connected blocks. It is guaranteed that the graph (with vertices 1 to N and an edge between u and v whenever \(u<v\) and \(u|v\)) is connected.

Input Format Summary:
The first line contains an integer N.
The second line contains N integers, where the i-th integer represents the color of the i-th point.

Output Format Summary:
Output N-1 lines, each line containing two integers which represent an edge in the spanning tree. The list of edges is printed such that all edges connecting vertices of different colors (which maximize the connected block count) appear first (sorted by the sum of the endpoints and then by the smaller endpoint), followed by edges connecting vertices of the same color (sorted similarly).

---

Note: In this problem, a spanning tree is chosen from the available edges such that the total weight (i.e. the total number of edges connecting vertices with different colors) is maximized. This can be achieved by running a maximum spanning tree algorithm (e.g. Kruskal's algorithm with weight 1 for different-colored edges and 0 for same-colored edges). After obtaining the tree, sort the selected edges as described before output.

inputFormat

The input consists of two lines:

1. The first line contains a single integer N, representing the number of points.
2. The second line contains N space‐separated integers where the i-th integer is the color of point i.

outputFormat

Print exactly N-1 lines. Each line contains two space-separated integers u and v (with u < v) representing an edge of the spanning tree. The ordering of the edges must be as follows:

1. Edges that connect vertices of different colors come before edges that connect vertices of the same color.
2. Within each group, edges with a smaller sum (u+v) come first.
3. If the sums are equal, the edge with the smaller minimum vertex comes first.

sample

4
1 2 3 4

1 2
1 3
1 4

</p>