问题描述

给定一个有$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, v_2, \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, W_2, \ldots, W_N)$ 的最大美丽度，使得$A_i \\neq -1 \\implies W_i = A_i$。如果不存在最大美丽度，则输出-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 (a_j,b_j)$
• 在给定的图$G$中，从顶点$1$到顶点$N$存在一条路径。
• $A_i = -1$ 或者 $1\\leq A_i\\leq 10^{12}$

输入

输入数据的格式如下所示，从标准输入中获取：

$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

样例输出1

4

从顶点$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

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

样例输出2

1

从顶点$1$到顶点$N$有三条路径：$(1,2,4)$，$(1,3,4)$ 和 $(1,4)$。例如，序列$W = (5, 3, 7, 8)$ 的美丽度为$1$。

样例输入3

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

样例输出3

-1

例如，序列$W = (3, 10^{100}, 10^{100}, 7)$ 的美丽度为$10^{100}+10$。由于可以任意增加$W$的美丽度，因此不存在最大美丽度。

样例输入4

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

样例输出4

9