#P13226. [ARC144E] GCD of Path Weights

    ID: 12409 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400图论数论DFS差分约束数学构造

[ARC144E] GCD of Path Weights

题目描述

给定一个有 NN 个顶点、MM 条边的有向图 GG。顶点编号为 1,2,…,N1, 2, \ldots, N。第 ii 条边是从 aia_i 指向 bib_i 的有向边,且 ai<bia_i < b_i。

定义正整数序列 W=(W1,W2,…,WN)W = (W_1, W_2, \ldots, W_N) 的美丽度为:满足下述条件的正整数 xx 的最大值。

  • 对于 GG 中从顶点 11 到顶点 NN 的任意一条路径 (v1,…,vk)(v_1, \ldots, v_k)(v1=1,vk=Nv_1 = 1, v_k = N),都有 ∑i=1kWvi\sum_{i=1}^k W_{v_i} 是 xx 的倍数。

给定整数序列 A=(A1,A2,…,AN)A = (A_1, A_2, \ldots, A_N)。请你构造正整数序列 W=(W1,…,WN)W = (W_1, \ldots, W_N),使得 Ai≠−1A_i \neq -1 时 Wi=AiW_i = A_i,并求出所有可能的 WW 的美丽度的最大值。如果最大值不存在,则输出 -1。

输入格式

输入按以下格式从标准输入给出。

NN MM
a1a_1 b1b_1
⋮\vdots
aMa_M bMb_M
A1A_1 A2A_2 …\ldots ANA_N

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

4

输入输出样例 #2

输入 #2

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

输出 #2

1

输入输出样例 #3

输入 #3

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

输出 #3

-1

输入输出样例 #4

输入 #4

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

输出 #4

9

说明/提示

限制条件

  • 2≤N≤3×1052 \leq N \leq 3 \times 10^5
  • 1≤M≤3×1051 \leq M \leq 3 \times 10^5
  • 1≤ai<bi≤N1 \leq a_i < b_i \leq N
  • 若 i≠ji \neq j,则 (ai,bi)≠(bj,aj)(a_i, b_i) \neq (b_j, a_j)
  • 给定的图 GG 中,存在从顶点 11 到顶点 NN 的路径。
  • Ai=−1A_i = -1 或 1≤Ai≤10121 \leq A_i \leq 10^{12}

样例解释 1

从顶点 11 到顶点 NN 的路径有 (1,2,4)(1,2,4) 和 (1,3,4)(1,3,4) 共两条。例如 W=(5,3,7,8)W = (5, 3, 7, 8) 的美丽度为 44。实际上,W1+W2+W4=16W_1 + W_2 + W_4 = 16,W1+W3+W4=20W_1 + W_3 + W_4 = 20,两者都是 44 的倍数。

样例解释 2

从顶点 11 到顶点 NN 的路径有 (1,2,4)(1,2,4)、(1,3,4)(1,3,4)、(1,4)(1,4) 共三条。例如 W=(5,3,7,8)W = (5, 3, 7, 8) 的美丽度为 11。

样例解释 3

例如 W=(3,10100,10100,7)W = (3, 10^{100}, 10^{100}, 7) 的美丽度为 10100+1010^{100} + 10。因为 WW 的美丽度可以无限大,所以最大值不存在。