Sea, You & copriMe

Think of the array as a graph.

Each index is a vertex. Put an edge between indices $i$ and $j$ when

$$\gcd(a_i,a_j)=1.$$

Now the task is exactly to find two disjoint edges, meaning a matching of size $2$.

The obvious all-pairs check is $O(n^2)$, which is dead on arrival. We need two ingredients:

1. a fast way to find any coprime pair inside a chosen active set,
2. a graph trick showing that only a constant number of such searches are needed.

Finding a coprime pair in an active set

Suppose some indices are currently active. For every square-free divisor $d$, define $cnt[d]$ as the number of active values divisible by $d$.

For a fixed active value $x$, the number of active values coprime to $x$ is

$$\sum_{d\mid x}\mu(d)cnt[d].$$

This is just Mobius inversion. A value $y$ contributes

$$\sum_{d\mid x,\ d\mid y}\mu(d),$$

which equals $1$ if $\gcd(x,y)=1$, and $0$ otherwise. That is inclusion-exclusion over the prime factors of $x$.

There is one small gotcha: if $x=1$, this count includes the index itself, since $\gcd(1,1)=1$. So for value $1$, subtract $1$ before deciding whether a partner exists.

So findPair(active) works like this:

• clear divisor counters from the previous query,
• for every active value, add $1$ to all counters of its square-free divisors,
• scan active indices and compute the Mobius sum,
• once some index has a positive count, linearly scan the active set to recover an actual coprime partner.

That last scan is fine because we only run this whole query a constant number of times. No quadratic nonsense sneaks in.

Using one edge as an anchor

First, find any coprime pair in the whole array. Call it $(u,v)$.

If no such pair exists, there are no edges at all, so the answer is $0$.

Now delete both $u$ and $v$. If the remaining indices contain a coprime pair $(x,y)$, then $(u,v)$ and $(x,y)$ are disjoint edges. Output them and go home.

The only interesting case is when deleting both $u$ and $v$ leaves no edge. Then every edge in the entire graph touches $u$ or $v$.

If a matching of size $2$ still exists, it cannot use an edge completely outside $\{u,v\}$, because there is no such edge. Therefore it must look like this:

$$(u,x) \quad \text{and} \quad (v,y),$$

where $x$ and $y$ are outside $\{u,v\}$ and $x\ne y$.

So we test two asymmetric worlds.

Delete only $u$. If we find an edge that does not use $v$, then that edge is disjoint from $(u,v)$, so we are done. Otherwise the found edge has form $(v,z)$. Then we only need to know whether $u$ has a coprime neighbor outside $\{v,z\}$. If yes, output $(v,z)$ and that edge from $u$.

If that fails, delete only $v$ and do the symmetric check. This catches the annoying case where the first chosen $(v,z)$ used the only neighbor of $u$, but $v$ had another possible neighbor. Tiny case split, big payoff.

Correctness proof

First, findPair(active) is correct. For any active index with value $x$, the Mobius sum counts exactly the active indices whose values are coprime to $x$. The self-count only happens when $x=1$, and subtracting $1$ fixes it. Therefore findPair returns a pair exactly when the active set contains at least one coprime pair.

Now consider the main algorithm. If it cannot find even one initial edge $(u,v)$, then the graph has no edges, so two disjoint edges are impossible.

If after deleting $u$ and $v$ there is an edge $(x,y)$, then $(u,v)$ and $(x,y)$ are disjoint coprime pairs, so the output is valid.

Otherwise, no edge avoids both $u$ and $v$. If a valid answer exists, its two disjoint edges must each touch one of $u$ and $v$. Since the edges are disjoint, one must use $u$ and the other must use $v$.

When we delete only $u$, any found edge either avoids $v$ or has form $(v,z)$. If it avoids $v$, it is disjoint from $(u,v)$ and we are done. If it is $(v,z)$, then the only way to pair it with an edge from $u$ is to find a coprime neighbor of $u$ outside $\{v,z\}$, which the algorithm checks directly.

If that direct check fails, then all possible neighbors of $u$ outside $v$ are contained in the single vertex $z$. Any remaining valid matching must therefore use $(u,z)$ and some edge from $v$ to a different vertex. The symmetric delete-$v$ check finds exactly that if it exists.

So every possible matching structure is covered. The algorithm only outputs after checking distinct indices and both gcd conditions, so every nonzero output is valid. If it outputs $0$, all possible structures have been ruled out.

Complexity

For a value $x\le 10^6$, the number of square-free divisors is $2^{\omega(x)}$, at most $128$. Each findPair query costs

$$O\left(\sum 2^{\omega(a_i)} + n\log A\right)$$

over its active indices, and we run only a constant number of queries per test case. Precomputing smallest prime factors up to $10^6$ is $O(10^6)$.

This comfortably fits the limits.