AT_tkppc6_2_j Common Divisors Shortest Path Queries

给定一个由 $N$ 个顶点组成的无向图。图的边信息由长度为 $N$ 的数列 $A$ 表示，具体如下： + 对于任意的整数对 $(i,j)$$（1\le i

输入通过标准输入给出，具体格式如下： > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ \text{query}_1 $ $ \text{query}_2 $ $ \cdots $ $ \text{query}_Q $ 第 $i$ 个查询的内容由 $ \text{query}_i $ 表示，格式如下： > $ S $ $ T $

输出通过标准输出给出，具体格式如下： 按顺序输出 $Q$ 行。第 $i$ 行表示第 $i$ 个查询的答案，具体如下： + 如果顶点 $S$ 和顶点 $T$ 连通，则输出从 $S$ 到 $T$ 的最短路径长度。 + 如果顶点 $S$ 和顶点 $T$ 不连通，则输出 `-1`。

### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ Q\ \leq\ 2\ \times\ 10^3 $ - $ 1\ \leq\ A_i\ \leq\ 10^6 $ $ (1\ \leq\ i\ \leq\ N) $ - 各クエリにおいて、$ 1\ \leq\ S,T\ \leq\ N $ かつ $ S\ \neq\ T $ が満たされる - 入力は全て整数 ### 部分点 - $ Q=1 $ を満たすデータセットに正解した場合、$ 500 $ 点が与えられる。 ### 注意 部分点のみを狙ったコードを提出する際には、$ Q $ が $ 1 $ より大きいならすぐ終了するといった処理を書き加えることを推奨します。 ### Sample Explanation 1 与えられる $ N=3 $ 頂点のグラフには、以下の $ 2 $ 本の辺が張られています。 - 頂点 $ 1 $ と頂点 $ 2 $ を結ぶ、長さ $ 2 $ の辺 - 頂点 $ 2 $ と頂点 $ 3 $ を結ぶ、長さ $ 3 $ の辺 よって各クエリに対する答えは以下の通りとなります。 - $ 1 $ 個目のクエリにおいて問われている、頂点 $ 1 $ と頂点 $ 2 $ の最短距離は頂点 $ 1 $ と頂点 $ 2 $ を直接結ぶ辺の長さに等しく、その値は $ 2 $ である。 - $ 2 $ 個目のクエリにおいて問われている、頂点 $ 2 $ と頂点 $ 3 $ の最短距離は頂点 $ 2 $ と頂点 $ 3 $ を直接結ぶ辺の長さに等しく、その値は $ 3 $ である。 - $ 3 $ 個目のクエリにおいて問われている、頂点 $ 1 $ と頂点 $ 3 $ の最短距離は頂点 $ 1,2 $ を結ぶ辺の長さと頂点 $ 2,3 $ を結ぶ辺の長さの和に等しく、その値は $ 5 $ である。 ### Sample Explanation 2 与えられるグラフにおいて頂点 $ 1 $ と頂点 $ 2 $ は非連結であるため、`-1` を出力します。 なお、この入力は部分点の制約を満たします。 ### Sample Explanation 3 原案: \[primenumber\\\_zz\](https://atcoder.jp/users/primenumber\_zz)