← 返回题目列表

AtCoder · abc244_e

H. 炸弹王

中文机器翻译题面 查看原题

分数: 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
  • 有一条边直接连接Vertex A_i 和顶点 A_{i+1}.
  • 整数 X\ (X≠S,X≠T) 按顺序出现偶数次(可能为零) A.

由于答案可能非常大,请对答案求模 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
  • If 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

以下 4 序列满足条件:

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

另一方面, (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.