E - King Bombee 解説 /

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

配点 : 500 点

問題文

N 頂点 M 辺の単純無向グラフが与えられます。このグラフの頂点には 1 から N の番号が付けられており、辺には 1 から M の番号が付けられています。辺 i は頂点 U_i と頂点 V_i の間を結んでいます。

整数 K, S, T, X が与えられます。以下の条件を満たす数列 A = (A_0, A_1, \dots, A_K) は何通りありますか？

  • A_i は 1 以上 N 以下の整数
  • A_0 = S
  • A_K = T
  • 頂点 A_i と頂点 A_{i + 1} の間を直接結ぶ辺が存在する
  • 数列 A の中に整数 X\ (X≠S,X≠T) は偶数回出現する ( 0 回でも良い)

ただし、答えは非常に大きくなることがあるので、答えを 998244353 で割ったあまりを求めてください。

制約

  • 入力は全て整数
  • 2≤N≤2000
  • 1≤M≤2000
  • 1≤K≤2000
  • 1≤S,T,X≤N
  • X≠S
  • X≠T
  • 1≤U_i<V_i≤N
  • i≠j ならば (U_i, V_i)≠(U_j, V_j)

入力

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

N M K S T X
U_1 V_1
U_2 V_2
\vdots
U_M V_M

出力

答えを 998244353 で割ったあまりを出力せよ。

入力例 1

4 4 4 1 3 2
1 2
2 3
3 4
1 4

出力例 1

4
  • (1, 2, 1, 2, 3)
  • (1, 2, 3, 2, 3)
  • (1, 4, 1, 4, 3)
  • (1, 4, 3, 4, 3)

の 4 個が条件を満たします。(1, 2, 3, 4, 3) や (1, 4, 1, 2, 3) は 2 が奇数回出現するため、条件を満たしません。

入力例 2

6 5 10 1 2 3
2 3
2 4
4 6
3 6
1 5

出力例 2

0

グラフは連結であるとは限りません。

入力例 3

10 15 20 4 4 6
2 6
2 7
5 7
4 5
2 4
3 7
1 7
1 4
2 9
5 10
1 3
7 8
7 9
1 6
1 2

出力例 3

952504739

998244353 で割ったあまりを求めてください。

Score : 500 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered from 1 through N, and the edges are numbered from 1 through M. Edge i connects Vertex U_i and Vertex V_i.

You are given integers K, S, T, and X. How many sequences A = (A_0, A_1, \dots, A_K) are there satisfying the following conditions?

  • A_i is an integer between 1 and N (inclusive).
  • A_0 = S
  • A_K = T
  • There is an edge that directly connects Vertex A_i and Vertex A_{i+1}.
  • Integer X\ (X≠S,X≠T) appears even number of times (possibly zero) in sequence A.

Since the answer can be very large, find the answer modulo 998244353.

Constraints

  • All values in input are integers.
  • 2≤N≤2000
  • 1≤M≤2000
  • 1≤K≤2000
  • 1≤S,T,X≤N
  • X≠S
  • X≠T
  • 1≤U_i<V_i≤N
  • If i ≠ j, then (U_i, V_i) ≠ (U_j, V_j).

Input

Input is given from Standard Input in the following format:

N M K S T X
U_1 V_1
U_2 V_2
\vdots
U_M V_M

Output

Print the answer modulo 998244353.

Sample Input 1

4 4 4 1 3 2
1 2
2 3
3 4
1 4

Sample Output 1

4

The following 4 sequences satisfy the conditions:

  • (1, 2, 1, 2, 3)
  • (1, 2, 3, 2, 3)
  • (1, 4, 1, 4, 3)
  • (1, 4, 3, 4, 3)

On the other hand, (1, 2, 3, 4, 3) and (1, 4, 1, 2, 3) do not, since there are odd number of occurrences of 2.

Sample Input 2

6 5 10 1 2 3
2 3
2 4
4 6
3 6
1 5

Sample Output 2

0

The graph is not necessarily connected.

Sample Input 3

10 15 20 4 4 6
2 6
2 7
5 7
4 5
2 4
3 7
1 7
1 4
2 9
5 10
1 3
7 8
7 9
1 6
1 2

Sample Output 3

952504739

Find the answer modulo 998244353.