因为 a_S\mid a_S(a_S+1)，a_T\mid a_T(a_T+1)，2\mid \gcd(a_S(a_S+1),a_T(a_T+1))，于是此时 S\to T 已经连通。容易证明不论 a_S,a_T 取何值，都可以通过两次操作使得两点连通。
于是只需要判断答案是否可以是 0 或 1：
壹、答案为 0
此时 S 和 T 已经连通。观察到值域为 10^6 级别，而边的数量虽然很多，但是可以通过枚举倍数的方式来连接。因此对于每一个存在值的 x 都只需要枚举其倍数 kx，判断其是否有值。容易发现这样建边，边数是调和级数的。判断连通性只需要使用并查集即可。该部分时间复杂度为 O(\alpha n\log n)。
贰、答案为 1
考虑到 n\le 10^6 时，\omega(n)\le 7，且 \gcd(x,x+1)=1。因此考虑对于每一个 a_S，若存在一质数 p 使得 p\mid a_S 且 p\mid a_T+1，或 p\mid a_S+1 且 p\mid a_T，则可以对 S 或 T 执行恰好一次操作，使得图连通。又因为 \omega(a_i)\le 7，因此直接暴力处理每一个 a_i 和 a_i+1 的所有质因子即可。