102124: [AtCoder]ABC212 E - Safety Journey

Problem Statement

The Republic of AtCoder has $N$ cities, called City $1$, City $2$, $\ldots$, City $N$. Initially, there was a bidirectional road between every pair of different cities, but $M$ of these roads have become unusable due to deterioration over time. More specifically, for each $1\leq i \leq M$, the road connecting City $U_i$ and City $V_i$ has become unusable.

Takahashi will go for a $K$-day trip that starts and ends in City $1$. Formally speaking, a $K$-day trip that starts and ends in City $1$ is a sequence of $K+1$ cities $(A_0, A_1, \ldots, A_K)$ such that $A_0=A_K=1$ holds and for each $0\leq i\leq K-1$, $A_i$ and $A_{i+1}$ are different and there is still a usable road connecting City $A_i$ and City $A_{i+1}$.

Print the number of different $K$-day trips that start and end in City $1$, modulo $998244353$. Here, two $K$-day trips $(A_0, A_1, \ldots, A_K)$ and $(B_0, B_1, \ldots, B_K)$ are said to be different when there exists an $i$ such that $A_i\neq B_i$.

Constraints

• $2 \leq N \leq 5000$
• $0 \leq M \leq \min\left( \frac{N(N-1)}{2},5000 \right)$
• $2 \leq K \leq 5000$
• $1 \leq U_i<V_i \leq N$
• All pairs $(U_i, V_i)$ are pairwise distinct.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$ $K$
$U_1$ $V_1$
$:$
$U_M$ $V_M$

Output

Print the answer.

Sample Input 1

3 1 4
2 3

Sample Output 1

4

There are four different trips as follows.

• ($1,2,1,2,1$)
• ($1,2,1,3,1$)
• ($1,3,1,2,1$)
• ($1,3,1,3,1$)

No other trip is valid, so we should print $4$.

Sample Input 2

3 3 3
1 2
1 3
2 3

Sample Output 2

0

No road remains usable, so there is no valid trip.

Sample Input 3

5 3 100
1 2
4 5
2 3

Sample Output 3

428417047

问题描述

在阿特科德共和国，有N个城市，分别叫做城市1，城市2，……，城市N。最初，每一对不同的城市之间都有双向道路，但由于时间的推移，其中的M条道路已经变得无法使用。具体来说，对于每个$1\leq i \leq M$，连接城市$U_i$和城市$V_i$的路已经变得无法使用。

高桥将要进行一次从城市1开始、结束的K天旅行。正式来说，一个从城市1开始、结束的K天旅行是一个由$K+1$个城市组成的序列$(A_0, A_1, \ldots, A_K)$，使得$A_0=A_K=1$成立，并且对于每个$0\leq i\leq K-1$，$A_i$和$A_{i+1}$是不同的，并且仍有一条连接城市$A_i$和城市$A_{i+1}$的可用道路。

输出从城市1开始、结束的不同K天旅行的数量，对998244353取模。这里，两个K天旅行$(A_0, A_1, \ldots, A_K)$和$(B_0, B_1, \ldots, B_K)$被认为是不同的，当存在一个$i$使得$A_i\neq B_i$时。

约束

• $2 \leq N \leq 5000$
• $0 \leq M \leq \min\left( \frac{N(N-1)}{2},5000 \right)$
• $2 \leq K \leq 5000$
• $1 \leq U_i<V_i \leq N$
• 所有对$(U_i, V_i)$都是互不相同的。
• 输入中的所有值都是整数。

输入

从标准输入中获取如下格式的输入：

$N$ $M$ $K$
$U_1$ $V_1$
$:$
$U_M$ $V_M$

输出

输出答案。

样例输入1

3 1 4
2 3

样例输出1

4

有四个不同的旅行如下。

• ($1,2,1,2,1$)
• ($1,2,1,3,1$)
• ($1,3,1,2,1$)
• ($1,3,1,3,1$)

没有其他有效的旅行，所以我们应该输出4。

样例输入2

3 3 3
1 2
1 3
2 3

样例输出2

0

没有道路仍然可用，所以没有有效的旅行。

样例输入3

5 3 100
1 2
4 5
2 3

样例输出3

428417047