配点 : 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