Score : $500$ points

问题描述

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

Takahashi将进行一场为期$K$天的旅行，起点和终点都在城市1。形式上来说，一场起点和终点均为城市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$。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 09:27:49