AT_abc244_e [ABC244E] 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$。
• 对于所有 $0 \leq i < K$，顶点 $A_i$ 和顶点 $A_{i+1}$ 之间存在直接相连的边。
• 在数列 $A$ 中，整数 $X$（且 $X \neq S, X \neq T$）出现的次数为偶数次（可以为 $0$ 次）。

由于答案可能非常大，请输出答案对 $998244353$ 取模的结果。

输入格式

输入按以下格式从标准输入读入。

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

输出格式

请输出答案对 $998244353$ 取模的结果。

输入输出样例 #1

输入 #1

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

输出 #1

4

输入输出样例 #2

输入 #2

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

输出 #2

0

输入输出样例 #3

输入 #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

说明/提示

限制条件

• 输入均为整数。
• $2 \leq N \leq 2000$
• $1 \leq M \leq 2000$
• $1 \leq K \leq 2000$
• $1 \leq S, T, X \leq N$
• $X \neq S$
• $X \neq T$
• $1 \leq U_i < V_i \leq N$
• 若 $i \neq j$，则 $(U_i, V_i) \neq (U_j, V_j)$

样例解释 1

• $(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

图不一定是连通的。

样例解释 3

请输出答案对 $998244353$ 取模的结果。

由 ChatGPT 4.1 翻译