AT_tupc2023_n.Do Not Turn Back

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个有 $N$ 个顶点、 $M$ 条边的无向连通简单图 $G$ ，顶点编号为 $1$ 到 $N$ ，边编号为 $1$ 到 $M$ 。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$ 。
给定一个正整数 $K$ ，请计算从顶点 $1$ 到顶点 $N$ 的长度为 $K$ 的路径（“歩道”），但不能连续经过同一条边。输出满足以下所有条件的长度为 $K+1$ 的数列 $a=(a_0,a_1,\dots,a_K)$ 的个数，对 $998244353$ 取模。

$a_i$ 是 $1$ 到 $N$ 之间的整数（ $0 \leq i \leq K$ ）
$a_0 = 1$ , $a_K = N$
在 $G$ 中 $a_{i-1}$ 和 $a_i$ 之间有直接连接边（ $1 \leq i \leq K$ ）
$a_{i-2} \ne a_i$ （ $2 \leq i \leq K$ ）

输入格式

输入以如下格式从标准输入给出。

$N$ $M$ $K$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$

输出格式

请输出答案。

输入输出样例

输入#1
```
6 8 5
1 2
1 3
2 3
2 4
3 5
4 5
4 6
5 6
```
输出#1
```
2
```

输入#2

输出#2

输入#3

7 21 1000000000
1 2
1 3
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 5
4 6
4 7
5 6
5 7
6 7

输出#3

405422475

说明/提示

部分分

对于额外约束 $N \leq 15$ 的数据集，答对可得 $10$ 分。

样例解释 1

有 $1 \to 2 \to 3 \to 5 \to 4 \to 6, 1 \to 3 \to 2 \to 4 \to 5 \to 6$ 这两条路径满足条件。

样例解释 2

只要不是连续经过同一条边，同一条边可以多次经过。

数据范围

$3 \leq N \leq 100$
$N-1 \leq M \leq \dfrac{N(N-1)}{2}$
$1 \leq K \leq 10^9$
$1 \leq u_i < v_i \leq N$
当 $i \ne j$ 时， $(u_i,v_i) \neq (u_j,v_j)$
给定的图为无向连通简单图
输入均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页