102444: [AtCoder]ABC244 E - King Bombee

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$.

问题描述

给你一个简单的无向图，包含 N 个顶点和 M 条边。顶点编号为 1 到 N，边编号为 1 到 M。第 i 条边连接顶点 U_i 和顶点 V_i。

给你整数 K、S、T 和 X。满足以下条件的序列 A = (A_0, A_1, ..., A_K) 有多少个？

• A_i 是 1 到 N 之间的整数（包括 1 和 N）。
• A_0 = S
• A_K = T
• 存在一条直接连接顶点 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
• 如果 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。