← 返回题目列表

AtCoder · arc144_e

E. 路径权重的 GCD

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

给你一个有向图 G 与 N 顶点和 M 边缘。顶点已编号 1, 2, \ldots, N。的 i第一条边从顶点定向 a_i 到顶点 b_i,其中 a_i < b_i.

的 美丽 正整数序列 W = (W_1, W_2, \ldots, W_N) 定义为最大正整数 x 满足以下条件:

  • 对于每条路径 (v_1, \ldots, v_k) (v_1 = 1, v_k = N) 来自顶点 1 到顶点 N in G, \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.

约束

  • 2\leq N\leq 3\times 10^5
  • 1\leq M\leq 3\times 10^5
  • 1\leq a_i < b_i \leq N
  • (a_i,b_i)\neq (a_j,b_j) if i\neq j
  • 在给定的图中 G,有一条来自 Vertex 的路径 1 到顶点 N.
  • A_i = -1 or 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

从 Vertex 有两条路径 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

从 Vertex 出发有 3 条路径 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