AT_arc144_e [ARC144E] GCD of Path Weights

给定一个有 $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$ 时 $W_i = A_i$，并求出所有可能的 $W$ 的美丽度的最大值。如果最大值不存在，则输出 `-1`。

输入按以下格式从标准输入给出。 > $N$ $M$ > $a_1$ $b_1$ > $\vdots$ > $a_M$ $b_M$ > $A_1$ $A_2$ $\ldots$ $A_N$

输出正整数序列 $W$ 的美丽度可能取得的最大值。如果最大值不存在，则输出 `-1`。

## 限制条件 - $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 (b_j, a_j)$ - 给定的图 $G$ 中，存在从顶点 $1$ 到顶点 $N$ 的路径。 - $A_i = -1$ 或 $1 \leq A_i \leq 10^{12}$ ## 样例解释 1 从顶点 $1$ 到顶点 $N$ 的路径有 $(1,2,4)$ 和 $(1,3,4)$ 共两条。例如 $W = (5, 3, 7, 8)$ 的美丽度为 $4$。实际上，$W_1 + W_2 + W_4 = 16$，$W_1 + W_3 + W_4 = 20$，两者都是 $4$ 的倍数。 ## 样例解释 2 从顶点 $1$ 到顶点 $N$ 的路径有 $(1,2,4)$、$(1,3,4)$、$(1,4)$ 共三条。例如 $W = (5, 3, 7, 8)$ 的美丽度为 $1$。 ## 样例解释 3 例如 $W = (3, 10^{100}, 10^{100}, 7)$ 的美丽度为 $10^{100} + 10$。因为 $W$ 的美丽度可以无限大，所以最大值不存在。 由 ChatGPT 4.1 翻译