题目描述

给定一个有 $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。

样例 1

输入

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

输出

4

样例 2

输入

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

输出

1

样例 3

输入

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

输出

-1

样例 4

输入

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 (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 翻译