G - Random Walk to Millionaire 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

N 個の頂点と M 本の辺からなる連結かつ単純な無向グラフが与えられます。
i = 1, 2, \ldots, M について、i 番目の辺は頂点 u_i と頂点 v_i を結んでいます。

高橋君は、はじめレベルが 0 の状態で頂点 1 におり、下記の行動をちょうど K 回行います。

  • まず、いまいる頂点に隣接する頂点の中から、1 つを等確率でランダムに選択し、その頂点に移動する。
  • その後、移動後の頂点 v に応じて、下記のイベントが発生します。
    • C_v = 0 のとき : 高橋君のレベルが 1 だけ増加する。
    • C_v = 1 のとき : 高橋君のいまのレベルを X とする。高橋君は X^2 円のお金を獲得する。

上記の K 回の行動の過程で高橋君が獲得するお金の合計金額の期待値を \mathrm{mod}\, 998244353 で出力してください（注記参照）。

注記

求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を求めてください。

制約

  • 2 \leq N \leq 3000
  • N-1 \leq M \leq \min\lbrace N(N-1)/2, 3000\rbrace
  • 1 \leq K \leq 3000
  • 1 \leq u_i, v_i \leq N
  • u_i \neq v_i
  • i \neq j \implies \lbrace u_i, v_i\rbrace \neq \lbrace u_j, v_j \rbrace
  • 与えられるグラフは連結
  • C_i \in \lbrace 0, 1\rbrace
  • 入力はすべて整数

入力

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

N M K
u_1 v_1
u_2 v_2
\vdots
u_M v_M
C_1 C_2 \ldots C_N

出力

答えを出力せよ。

入力例 1

5 4 8
4 5
2 3
2 4
1 2
0 0 1 1 0

出力例 1

89349064

高橋君の移動経路として考えられるものは複数ありますが、ここでは例として、高橋君が頂点 1 を始点として、1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 と移動する場合に獲得するお金の合計金額を計算します。

  1. 高橋君は 1 回目の行動で、いまいる頂点 1 に隣接する頂点 2 に移動します。C_2 = 0 であるため、その後高橋君のレベルが 1 に上がります。
  2. 高橋君は 2 回目の行動で、いまいる頂点 2 に隣接する頂点 4 に移動します。C_4 = 1 であるため、その後高橋君は 1^2 = 1 円を獲得します。
  3. 高橋君は 3 回目の行動で、いまいる頂点 4 に隣接する頂点 5 に移動します。C_5 = 0 であるため、その後高橋君のレベルが 2 に上がります。
  4. 高橋君は 4 回目の行動で、いまいる頂点 5 に隣接する頂点 4 に移動します。C_4 = 1 であるため、その後高橋君は 2^2 = 4 円を獲得します。
  5. 高橋君は 5 回目の行動で、いまいる頂点 4 に隣接する頂点 2 に移動します。C_2 = 0 であるため、その後高橋君のレベルが 3 に上がります。
  6. 高橋君は 6 回目の行動で、いまいる頂点 2 に隣接する頂点 1 に移動します。C_1 = 0 であるため、その後高橋君のレベルが 4 に上がります。
  7. 高橋君は 7 回目の行動で、いまいる頂点 1 に隣接する頂点 2 に移動します。C_2 = 0 であるため、その後高橋君のレベルが 5 に上がります。
  8. 高橋君は 8 回目の行動で、いまいる頂点 2 に隣接する頂点 3 に移動します。C_3 = 1 であるため、その後高橋君は 5^2 = 25 円を獲得します。

よって、高橋君が獲得するお金の合計金額は、1 + 4 + 25 = 30 円です。

入力例 2

8 12 20
7 6
2 6
6 4
2 1
8 5
7 2
7 5
3 7
3 5
1 8
6 3
1 4
0 0 1 1 0 0 0 0

出力例 2

139119094

Score : 600 points

Problem Statement

You are given a connected simple undirected graph consisting of N vertices and M edges.
For i = 1, 2, \ldots, M, the i-th edge connects vertex u_i and vertex v_i.

Takahashi starts at Level 0 on vertex 1, and will perform the following action exactly K times.

  • First, choose one of the vertices adjacent to the vertex he is currently on, uniformly at random, and move to the chosen vertex.
  • Then, the following happens according to the vertex v he has moved to.
    • If C_v = 0: Takahashi's Level increases by 1.
    • If C_v = 1: Takahashi receives a money of X^2 yen, where X is his current Level.

Print the expected value of the total amount of money Takahashi receives during the K actions above, modulo 998244353 (see Notes).

Notes

It can be proved that the sought expected value is always a rational number. Additionally, under the Constraints of this problem, when that value is represented as \frac{P}{Q} using two coprime integers P and Q, it can also be proved that there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Find this R.

Constraints

  • 2 \leq N \leq 3000
  • N-1 \leq M \leq \min\lbrace N(N-1)/2, 3000\rbrace
  • 1 \leq K \leq 3000
  • 1 \leq u_i, v_i \leq N
  • u_i \neq v_i
  • i \neq j \implies \lbrace u_i, v_i\rbrace \neq \lbrace u_j, v_j \rbrace
  • The given graph is connected.
  • C_i \in \lbrace 0, 1\rbrace
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N M K
u_1 v_1
u_2 v_2
\vdots
u_M v_M
C_1 C_2 \ldots C_N

Output

Print the answer.

Sample Input 1

5 4 8
4 5
2 3
2 4
1 2
0 0 1 1 0

Sample Output 1

89349064

Among the multiple paths that Takahashi may traverse, let us take a case where Takahashi starts on vertex 1 and goes along the path 1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3, and compute the total amount of money he receives.

  1. In the first action, he moves from vertex 1 to an adjacent vertex, vertex 2. Then, since C_2 = 0, his Level increases to 1.
  2. In the second action, he moves from vertex 2 to an adjacent vertex, vertex 4. Then, since C_4 = 1, he receives 1^2 = 1 yen.
  3. In the third action, he moves from vertex 4 to an adjacent vertex, vertex 5. Then, since C_5 = 0, his Level increases to 2.
  4. In the fourth action, he moves from vertex 5 to an adjacent vertex, vertex 4. Then, since C_4 = 1, he receives 2^2 = 4 yen.
  5. In the fifth action, he moves from vertex 4 to an adjacent vertex, vertex 2. Then, since C_2 = 0, his Level increases to 3.
  6. In the sixth action, he moves from vertex 2 to an adjacent vertex, vertex 1. Then, since C_1 = 0, his Level increases to 4.
  7. In the seventh action, he moves from vertex 1 to an adjacent vertex, vertex 2. Then, since C_2 = 0, his Level increases to 5.
  8. In the eighth action, he moves from vertex 2 to an adjacent vertex, vertex 3. Then, since C_3 = 1, he receives 5^2 = 25 yen.

Thus, he receives a total of 1 + 4 + 25 = 30 yen.

Sample Input 2

8 12 20
7 6
2 6
6 4
2 1
8 5
7 2
7 5
3 7
3 5
1 8
6 3
1 4
0 0 1 1 0 0 0 0

Sample Output 2

139119094