← 返回题目列表

Codeforces · 1662/C

C. 欧洲之旅

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

欧洲地图可以用一组 $$$n$$$ 城市表示,编号从 $$$1$$$ 到 $$$n$$$,这些城市由 $$$m$$$ 双向道路连接,每条道路连接两个不同的城市。长度为 $$$k$$$ 的行程是 $$$k+1$$$ 城市 $$$v_1, v_2, \ldots, v_{k+1}$$$ 的序列,这样对于所有 $$$1 \le i \le k$$$ 来说,都有一条道路连接每对连续的城市 $$$v_i$$$、$$$v_{i+1}$$$。特殊旅行是指不连续两次使用同一条道路的旅行,即 $$$k+1$$$ 城市 $$$v_1, v_2, \ldots, v_{k+1}$$$ 的序列,这样它就形成一个旅行和 $$$v_i \neq v_{i + 2}$$$,对于所有 $$$1 \le i \le k - 1$$$。

给定一个整数 $$$k$$$,计算长度为 $$$k$$$ 且在同一城市开始和结束的不同特殊旅行的数量。由于答案可能很大,请以 $$$998\,244\,353$$$ 为模给出答案。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$3 \le n \le 100$$$, $$$1 \le m \le n(n - 1) / 2$$$, $$$1 \le k \le 10^4$$$) — 城市数量、道路数量和行程长度考虑。

以下 $$$m$$$ 行中的每一行都包含一对不同的整数 $$$a$$$ 和 $$$b$$$ ($$$1 \le a, b \le n$$$) — 每对代表一条连接城市 $$$a$$$ 和 $$$b$$$ 的道路。保证道路是不同的(即每对城市最多由一条道路连接)。

输出

打印长度为 $$$k$$$ 且在同一城市开始和结束的特殊行程的数量,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

4 5 2
4 1
2 3
3 1
4 3
2 4

输出 #1

0

输入 #2

4 5 3
1 3
4 2
4 1
2 1
3 4

输出 #2

12

输入 #3

8 20 12
4 3
6 7
5 7
8 2
8 3
3 1
4 7
8 5
5 4
3 5
7 1
5 1
7 8
3 2
4 2
5 2
1 4
4 8
3 6
4 6

输出 #3

35551130

注意

在第一个示例中,我们正在寻找长度 $$$2$$$ 的特殊旅行,但由于一旦我们离开一个城市,我们就不能再回去,所以我们不能两次使用同一条道路,所以答案是 $$$0$$$。

在第二个示例中,我们有以下 $$$12$$$ 特殊行程,长度为 $$$3$$$,在同一城市开始和结束:$$$(1, 2, 4, 1)$$$, $$$(1, 3, 4, 1)$$$, $$$(1, 4, 2, 1)$$$, $$$(1, 4, 3, 1)$$$, $$$(2, 1, 4, 2)$$$, $$$(2, 4, 1, 2)$$$, $$$(3, 1, 4, 3)$$$, $$$(3, 4, 1, 3)$$$, $$$(4, 1, 3, 4)$$$, $$$(4, 3, 1, 4)$$$、$$$(4、1、2、4)$$$ 和 $$$(4、2、1、4)$$$。