[ARC144E] GCD of Path Weights

给定 $n$ 个点，$m$ 条边的有向图，图中的任意一条有向边满足 **边起点的编号小于边终点的编号**。每个点有点权，但其中有些点的点权未知。 你需要找到一种给未知点权值的方案，使得 **所有 $1\to n$ 的路径点权和的最大公因数最大**，或者告知答案可以无限大。输出这个最大值。 $n,m\le 3\times 10^5$。

[problemUrl]: https://atcoder.jp/contests/arc144/tasks/arc144_e $ N $ 頂点 $ M $ 辺からなる有向グラフ $ G $ が与えられます．頂点には $ 1,\ 2,\ \ldots,\ N $ の番号がついています．$ i $ 番目の辺は $ a_i $ から $ b_i $ に向かう有向辺で，$ a_i\ <\ b_i $ が成り立っています． 正整数列 $ W\ =\ (W_1,\ W_2,\ \ldots,\ W_N) $ の**美しさ**を，次が成り立つような正整数 $ x $ の最大値として定義します． - $ G $ における頂点 $ 1 $ から頂点 $ N $ への任意のパス $ (v_1,\ \ldots,\ v_k) $ ($ v_1\ =\ 1,\ v_k\ =\ N $) に対し，$ \sum_{i=1}^k\ W_{v_i} $ は $ x $ の倍数である． 整数列 $ A\ =\ (A_1,\ A_2,\ \ldots,\ A_N) $ が与えられます．正整数列 $ W\ =\ (W_1,\ \ldots,\ W_N) $ を，$ A_i\ \neq\ -1\ \implies\ W_i\ =\ A_i $ を満たすように定めるとき，その美しさとしてありうる最大値を求めてください．ただし，最大値が存在しない場合には `-1` を出力してください．

入力は以下の形式で標準入力から与えられます． > $ N $ $ M $ $ a_1 $ $ b_1 $ $ \vdots $ $ a_M $ $ b_M $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

正整数列 $ W $ の美しさとしてありうる最大値を出力してください．ただし，最大値が存在しない場合には `-1` を出力してください．

4 4
1 2
1 3
2 4
3 4
-1 3 7 -1

4

4 5
1 2
1 3
2 4
3 4
1 4
-1 3 7 -1

1

4 4
1 2
1 3
2 4
3 4
3 -1 -1 7

-1

5 5
1 3
3 5
2 3
3 4
1 4
2 -1 3 -1 4

9

### 制約 - $ 2\leq\ N\leq\ 3\times\ 10^5 $ - $ 1\leq\ M\leq\ 3\times\ 10^5 $ - $ 1\leq\ a_i\ <\ b_i\ \leq\ N $ - $ i\neq\ j $ ならば $ (a_i,b_i)\neq\ (a_j,b_j) $ - 与えられるグラフ $ G $ において，頂点 $ 1 $ から頂点 $ N $ へのパスが存在する． - $ A_i\ =\ -1 $ または $ 1\leq\ A_i\leq\ 10^{12} $ ### Sample Explanation 1 頂点 $ 1 $ から頂点 $ N $ へのパスは，$ (1,2,4) $, $ (1,3,4) $ の $ 2 $ 個です． 例えば $ W\ =\ (5,\ 3,\ 7,\ 8) $ の美しさは $ 4 $ となります．実際，$ W_1\ +\ W_2\ +\ W_4\ =\ 16 $, $ W_1\ +\ W_3\ +\ W_4\ =\ 20 $ はともに $ 4 $ の倍数です． ### Sample Explanation 2 頂点 $ 1 $ から頂点 $ N $ へのパスは，$ (1,2,4) $, $ (1,3,4) $, $ (1,4) $ の $ 3 $ 個です． 例えば $ W\ =\ (5,\ 3,\ 7,\ 8) $ の美しさは $ 1 $ となります． ### Sample Explanation 3 例えば $ W\ =\ (3,\ 10^{100},\ 10^{100},\ 7) $ の美しさは $ 10^{100}+10 $ となります．$ W $ の美しさをいくらでも大きくできるため，その最大値は存在しません．