P7854 「EZEC-9」GCD Tree

规定 $\gcd(x,y)$ 表示 $x,y$ 的最大公约数，$\operatorname{lca}(x,y)$ 表示 $x$ 号节点和 $y$ 号节点的最近公共祖先。

给你 $n$ 个点，编号分别为 $1,2,\ldots,n$，点权分别为 $a_1,a_2,\ldots,a_n$。 请你用这 $n$ 个点构造一棵树，使得 $\forall 1 \le i < j \le n$，$\gcd(a_i, a_j) = a_{\operatorname{lca}(i, j)}$。 若无解，报告之，否则输出树的形态。

无

无

**【数据规模与约定】** **本题采用捆绑测试。** - Subtask 1（5 points）：$n = 2$。 - Subtask 2（5 points）：所有 $a_i$ 均相等。 - Subtask 3（5 points）：$n \le 5$。 - Subtask 4（10 points）：保证有解。 - Subtask 5（15 points）：$n \le 100$。 - Subtask 6（15 points）：$n \le 10^3$。 - Subtask 7（15 points）：$n \le 3 \times 10^3$。 - Subtask 8（30 points）：无特殊限制。 对于 $100 \%$ 的数据，$2 \le n \le 10^5$，$1 \le a_i \le 10^6$。