E - Tree and Back Edges Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 1000

問題文

1 から N までの番号のついた N 頂点からなる根付き木 T があります. 根は頂点 1 で,頂点 i (2 \leq i \leq N) の親は頂点 P_i (P_i<i) です. この木の辺は有向辺で,各辺は親から子の方向へ向いています.

あなたは TM 本の辺を追加し,有向グラフ G を作りました. i 番目に追加した辺は,頂点 A_i から頂点 B_i へ向かう辺でした. ここで,A_i,B_i は以下の条件を満たすことが保証されます.

  • 1 \leq B_i<A_i \leq N
  • T において頂点 A_i は頂点 B_i の子孫である
  • T において頂点 A_i は葉でない

なお,同じ辺を複数本追加することもありえます.

あなたはこれから G の頂点 1 からスタートし,停止するまで次の操作を繰り返します.

  • 今いる頂点から出る辺が存在しないなら停止する.
  • 今いる頂点から出る辺が存在するなら,そのうちの 1 つを一様ランダムに選び,その辺が向かう頂点へ移動する.

停止するまでに移動する回数の期待値を\pmod{P} で求めてください.

ただしこの問題では P の値は入力で与えられません. そのかわり,以下の制約をすべて満たすような P をあなたが選び,その P に対して問題を解いてください.

  • P は素数
  • 998244353 \leq P < 2 \times 10^9
  • \pmod{P} で答えが定義できる
期待値 \pmod{P} の定義

求める期待値は必ず有理数になることが証明できます. その値を既約分数 \frac{P}{Q} で表した時,Q \neq 0 \pmod{P} となっていればこの値は\pmod{P} で定義できると言い,Q = 0 \pmod{P} ならば定義できないと言います.値が定義できる場合,R \times Q \equiv P \pmod{P}, 0 \leq R < P を満たす整数 R が一意に定まります. この R を答えてください.

この問題のジャッジについて

ジャッジはまず,あなたの選んだ P が最初の 2 つの条件を満たすかどうかチェックします. 条件を満たさない場合は,そのテストケースは不正解と判定します. 条件を満たす場合,ジャッジはこの P に対して問題を解くプログラムを実行します. ジャッジが答え\pmod{P} の値を計算できる場合,それをあなたの出力と比較して正誤判定を行います. ジャッジが答え\pmod{P} を計算できないが, 答えが\pmod{P} で定義できないと判断できる場合,そのテストケースは不正解と判定します. ジャッジが答え\pmod{P} を計算できず,かつ 答えが\pmod{P} で定義できるか否かが判断できない場合は,そのテストケースは正解と判定します. なお,この問題の制約下で,最初の 2 つの条件を満たす P のうち 99.9% 以上で期待値が定義でき,かつジャッジがそれを正しく計算できることが証明できます.

制約

  • 2 \leq N \leq 250000
  • 0 \leq M \leq 250000
  • 1 \leq P_i < i
  • 1 \leq B_i<A_i \leq N
  • T において頂点 A_i は頂点 B_i の子孫である
  • T において頂点 A_i は葉でない
  • 入力される値はすべて整数
  • サンプル以外のテストケースは 50 個以下である.

入力

入力は以下の形式で標準入力から与えられる.

N M
P_2 P_3 \cdots P_N
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

答えを以下の形式で出力せよ.

ans P

ここで P はあなたが選んだ素数であり,ans\pmod{P} での答えである.


入力例 1

3 0
1 2

出力例 1

2 998244353

入力例 2

3 1
1 2
2 1

出力例 2

4 998244353

入力例 3

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

出力例 3

453747441 998244353

入力例 4

20 25
1 2 3 2 5 2 6 1 9 2 2 12 13 1 2 16 17 16 19
13 12
12 1
17 1
6 5
5 1
13 12
12 2
17 16
17 16
17 16
19 16
6 5
16 2
6 5
9 1
9 1
13 12
13 12
6 5
19 16
6 5
17 16
6 5
13 1
13 12

出力例 4

529789893 998244353