← 返回题目列表

AtCoder · abc212_e

H. 安全之旅

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

分数: 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