E - GCD of Path Weights Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

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 \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) の 2 個です． 例えば 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) の 3 個です． 例えば 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

Score : 800 points

Problem Statement

You are given a directed graph G with N vertices and M edges. The vertices are numbered 1, 2, \ldots, N. The i-th edge is directed from Vertex a_i to Vertex b_i, where a_i < b_i.

The beautifulness of a sequence of positive integers W = (W_1, W_2, \ldots, W_N) is defined as the maximum positive integer x that satisfies the following:

  • For every path (v_1, \ldots, v_k) (v_1 = 1, v_k = N) from Vertex 1 to Vertex N in G, \sum_{i=1}^k W_{v_i} is a multiple of x.

You are given an integer sequence A = (A_1, A_2, \ldots, A_N). Find the maximum beautifulness of a sequence of positive integers W = (W_1, \ldots, W_N) such that A_i \neq -1 \implies W_i = A_i. If the maximum beautifulness does not exist, print -1.

Constraints

  • 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
  • In the given graph G, there is a path from Vertex 1 to Vertex N.
  • A_i = -1 or 1\leq A_i\leq 10^{12}

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
\vdots
a_M b_M
A_1 A_2 \ldots A_N

Output

Print the maximum beautifulness of a sequence of positive integers W. If the maximum beautifulness does not exist, print -1.

Sample Input 1

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

Sample Output 1

4

There are two paths from Vertex 1 to Vertex N: (1,2,4) and (1,3,4). For instance, W = (5, 3, 7, 8) has a beautifulness of 4. Indeed, both W_1 + W_2 + W_4 = 16 and W_1 + W_3 + W_4 = 20 are multiples of 4.

Sample Input 2

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

Sample Output 2

1

There are three paths from Vertex 1 to Vertex N: (1,2,4), (1,3,4), and (1,4). For instance, W = (5, 3, 7, 8) has a beautifulness of 1.

Sample Input 3

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

Sample Output 3

-1

For instance, W = (3, 10^{100}, 10^{100}, 7) has a beautifulness of 10^{100}+10. Since you can increase the beautifulness of W as much as you want, there is no maximum beautifulness.

Sample Input 4

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

Sample Output 4

9