分数: 500 点
问题陈述
AtCoder 共和国有 N 城市,称为 City 1, 城市 2, \ldots, 城市 N。 最初,每对不同城市之间都有一条双向道路,但是 M 这些道路由于时间的推移而变得无法使用。更具体地说,对于每个 1\leq i \leq M, 连接城市的道路 U_i 和城市 V_i 已变得无法使用。
高桥会去 K- 以城市为起点和终点的一日游 1。正式来说,一个 K- 以城市为起点和终点的一日游 1 是一系列 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}.
打印不同的数量 K- 以城市为起点和终点的一日游 1,模数 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