AT_tkppc6_2_j Common Divisors Shortest Path Queries

[problemUrl]: https://atcoder.jp/contests/tkppc6-2/tasks/tkppc6_2_j $ N $ 頂点の無向グラフがあります。このグラフの辺の情報は長さ $ N $ の数列 $ A $ を用いて、以下のように表されます。 - 任意の整数対 $ (i,j)\ (1\ \leq\ i\ \lt\ j\ \leq\ N) $ について、 - $ A_i $ と $ A_j $ が互いに素なら、頂点 $ i $ と頂点 $ j $ の間に辺は存在しない。 - $ A_i $ と $ A_j $ が $ 1 $ より大きい公約数を持つなら、その中の最小値を $ x $ として頂点 $ i $ と頂点 $ j $ の間に長さ $ x $ の辺が存在する。 以下のクエリが $ Q $ 個与えられるので、順に処理してください。 - 頂点の組 $ (S,T) $ が与えられる。$ S $ と $ T $ が連結かを判定し、連結なら $ S $ から $ T $ へ向かう最短経路の長さを出力せよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ \text{query}_1 $ $ \text{query}_2 $ $ \hspace{0.4cm}\vdots $ $ \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)