← 返回题目列表

AtCoder · tupc2023_n

N. 不要回头

中文机器翻译题面 查看原题

配点 : 100 点

問題文

在顶部 编号为 1 减去 N 的编号与边 1 减去 M 有 N 頂点 M 边的简单连通无向图 G 。侧面 i\;(1 \leq i \leq M) 是顶点 是 u_i 和 按字典顺序比较 v_i 相连。 到
正整数 K ,所以顶点 1 到顶点 N 的长度 K 的人行道,并且不连续经过同一条边的数量为 998244353 除的余数。 用
严格来说,是满足以下所有条件的长度 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)

制約

  • 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)
  • 给定的图是单纯连通无向图
  • 所有输入均为整数

部分点

  • 附加限制 如果正确答案是满足 N \leq 15 的数据集 给出 10 点。 如果您正确回答了所有满足

入力

输入是按以下格式从标准输入给出的。

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

1 \to 2 \to 3 \to 5 \to 4 \to 6, 1 \to 3 \to 2 \to 4 \to 5 \to 6 可以得到第 2 满足条件。


入力例 2

11 11 2023
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
1 11

出力例 2

1

不连续则可以多次经过同一条边。


入力例 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