GCD of Reachable Nodes

2 secs 1024 MB
take44444's icon take44444

問題文

NN頂点MM辺の単純有向グラフが与えられます.(グラフは連結ではないこともあります.)ii1iM1 \leq i \leq M)本目の辺は頂点uiu_iから頂点viv_iへ張られています.
また,各頂点には,値AiA_i1iN1 \leq i \leq N)が書かれています.
全頂点について以下を求めてください.

その頂点から到達可能な頂点の集合SSについて,SSに含まれる頂点に書いてある数の最大公約数

ただし,頂点uuから頂点vvに"到達可能"とは,頂点uuから,有向辺に沿って頂点を 00回以上 移動することで頂点vvに到達可能であるということをいいます.

制約

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 1Mmin(N(N1),2×105)1 \leq M \leq \min(N (N-1), 2 \times 10^5)
  • 1ui,viN(1iM)1 \leq u_i, v_i \leq N \quad (1 \leq i \leq M)
  • uivi(1iM)u_i \neq v_i \quad (1 \leq i \leq M)
  • ij ならば (ui,vi)(uj,vj)(1i,jM)i \neq j \ ならば\ (u_i, v_i) \neq (u_j, v_j) \quad (1 \leq i, j \leq M)
  • 1Ai109(1iN)1 \leq A_i \leq 10^9 \quad (1 \leq i \leq N)
  • 入力はすべて整数

入力

N MN\ M
A1 A2ANA_1\ A_2 \dots A_N
u1 v1u_1\ v_1
u2 v2u_2\ v_2
\vdots
uM vMu_M\ v_M

出力

ii行目(1iN1 \leq i \leq N)に以下を出力.

頂点iiから到達可能な頂点の集合SiS_iについて,SiS_iに含まれる頂点に書いてある数の最大公約数

サンプル

入力例1
10 11
20 66 390 28 15 140 84 36 210 252
1 2
1 3
1 4
2 3
3 9
4 6
5 1
6 8
7 10
8 4
8 7
出力例1
2
6
30
4
1
4
84
4
210
252

Submit


Go (1.21)