← 返回题目列表

Codeforces · 997/D

D. 产品循环

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

考虑一棵树(即没有循环的无向连通图)$$$T_1$$$ 和一棵树$$$T_2$$$。让我们用以下方式定义他们的笛卡尔积 $$$T_1 \times T_2$$$ 。

设 $$$V$$$ 为 $$$T_1$$$ 中的顶点集,$$$U$$$ 为 $$$T_2$$$ 中的顶点集。

那么图 $$$T_1 \times T_2$$$ 的顶点集合是 $$$V \times U$$$,即一组有序的顶点对,其中第一个顶点对来自 $$$V$$$,第二个顶点来自 $$$U$$$。

让我们绘制以下边:

- 如果 $$$u_1$$$ 和 $$$u_2$$$ 在 $$$U$$$ 中相邻,则在 $$$(v, u_1)$$$ 和 $$$(v, u_2)$$$ 之间存在无向边。
- 同样,如果 $$$v_1$$$ 和 $$$v_2$$$ 在 $$$V$$$ 中相邻,则 $$$(v_1, u)$$$ 和 $$$(v_2, u)$$$ 之间存在无向边。

样品测试中的树木产品图片请参见备注部分。

让我们检查一下图表 $$$T_1 \times T_2$$$。它包含多少个长度为 $$$k$$$ 的循环(不一定简单)?由于这个数字可能非常大,因此打印它对 $$$998244353$$$ 取模。

顶点序列 $$$w_1$$$, $$$w_2$$$, ..., $$$w_k$$$,其中 $$$w_i \in V \times U$$$ 称为循环,如果任何相邻顶点相邻且 $$$w_1$$$ 与 $$$w_k$$$ 相邻。仅循环移位或遍历方向不同的循环仍然被认为是不同的。

输入

输入的第一行包含三个整数 - $$$n_1$$$、$$$n_2$$$ 和 $$$k$$$ ($$$2 \le n_1, n_2 \le 4000$$$, $$$2 \le k \le 75$$$) - 第一棵树中的顶点数、第二棵树中的顶点数和循环长度分别。

然后遵循描述第一棵树的 $$$n_1 - 1$$$ 行。每行包含两个整数 - $$$v_i, u_i$$$ ($$$1 \le v_i, u_i \le n_1$$$),它们定义第一棵树的边缘。

然后遵循 $$$n_2 - 1$$$ 行,它们以相同的格式描述第二棵树。

保证给定的图是树。

输出

打印一个整数 — 周期数以 $$$998244353$$$ 为模。

示例

输入 #1

2 2 2
1 2
1 2

输出 #1

8

输入 #2

2 2 4
1 2
1 2

输出 #2

32

输入 #3

2 3 4
1 2
1 2
1 3

输出 #3

70

输入#4

4 2 2
1 2
1 3
1 4
1 2

输出#4

20

注意

下面三张图片说明了图形,它们是样本测试的树木的产物。

在第一个示例中,长度为 $$$2$$$ 的循环列表如下:

- «AB», «BA»
- «BC», «CB»
- «AD», «DA»
- «CD», «DC»