King Bombee

题目描述

给出一个有 $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}$。 整数 $X\ (X≠S,X≠T)$ 在序列 $A$ 中出现偶数次（可能为零次）。

由于答案可能非常大，求答案对 $998244353$ 取模的值。

输入格式

输入从标准输入给出，格式如下： $N$ $M$ $K$ $S$ $T$ $X$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_M$ $V_M$

输出格式

输出对 $998244353$ 取模的答案。

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

4

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

0

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

952504739

提示

输入中的所有值都是整数。 $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)$。下面的 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$ 出现了奇数次。
图不一定是连通的。
答案对 $998244353$ 取模。

标签: AtCoder|abc244E

来源

AtCoder|abc244E