English · Original
Chinese · Translation
Formal · Original
Consider a tree (that is, an undirected connected graph without loops) $T_1$ and a tree $T_2$. Let's define their _cartesian product_ $T_1 \times T_2$ in a following way.
Let $V$ be the set of vertices in $T_1$ and $U$ be the set of vertices in $T_2$.
Then the set of vertices of graph $T_1 \times T_2$ is $V \times U$, that is, a set of ordered pairs of vertices, where the first vertex in pair is from $V$ and the second — from $U$.
Let's draw the following edges:
* Between $(v, u_1)$ and $(v, u_2)$ there is an undirected edge, if $u_1$ and $u_2$ are adjacent in $U$.
* Similarly, between $(v_1, u)$ and $(v_2, u)$ there is an undirected edge, if $v_1$ and $v_2$ are adjacent in $V$.
Please see the notes section for the pictures of products of trees in the sample tests.
Let's examine the graph $T_1 \times T_2$. How much cycles (not necessarily simple) of length $k$ it contains? Since this number can be very large, print it modulo $998244353$.
The sequence of vertices $w_1$, $w_2$, ..., $w_k$, where $w_i \in V \times U$ called cycle, if any neighboring vertices are adjacent and $w_1$ is adjacent to $w_k$. Cycles that differ only by the cyclic shift or direction of traversal are still considered **different**.
## Input
First line of input contains three integers — $n_1$, $n_2$ and $k$ ($2 \le n_1, n_2 \le 4000$, $2 \le k \le 75$) — number of vertices in the first tree, number of vertices in the second tree and the cycle length respectively.
Then follow $n_1 - 1$ lines describing the first tree. Each of this lines contains two integers — $v_i, u_i$ ($1 \le v_i, u_i \le n_1$), which define edges of the first tree.
Then follow $n_2 - 1$ lines, which describe the second tree in the same format.
It is guaranteed, that given graphs are trees.
## Output
Print one integer — number of cycles modulo $998244353$.
[samples]
## Note
The following three pictures illustrate graph, which are products of the trees from sample tests.
In the first example, the list of cycles of length $2$ is as follows:
* «AB», «BA»
* «BC», «CB»
* «AD», «DA»
* «CD», «DC»
<center>  </center>
考虑一棵树（即无环的无向连通图）$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$。
我们添加如下边：
请参见注释部分以查看示例测试中树的乘积图。
现在考察图 $T_1 \times T_2$。它包含多少个长度为 $k$ 的环（不一定是简单环）？由于这个数可能非常大，请输出对 $998244353$ 取模的结果。
一个顶点序列 $w_1, w_2, \dots, w_k$，其中 $w_i \in V \times U$，被称为环，当且仅当任意相邻顶点均相邻，且 $w_1$ 与 $w_k$ 相邻。仅因循环移位或遍历方向不同而不同的环仍被视为 *不同* 的环。
输入的第一行包含三个整数 $n_1$, $n_2$ 和 $k$（$2 \leq n_1, n_2 \leq 4000$，$2 \leq k \leq 75$），分别表示第一棵树的顶点数、第二棵树的顶点数和环的长度。
随后有 $n_1 - 1$ 行描述第一棵树，每行包含两个整数 $v_i, u_i$（$1 \leq v_i, u_i \leq n_1$），表示第一棵树的边。
再随后有 $n_2 - 1$ 行，以相同格式描述第二棵树。
保证给定的图均为树。
请输出一个整数——环的数量对 $998244353$ 取模的结果。
下图展示了示例测试中树的乘积图。
在第一个例子中，长度为 $2$ 的环列表如下：
## Input
输入的第一行包含三个整数 $n_1$, $n_2$ 和 $k$（$2 \leq n_1, n_2 \leq 4000$，$2 \leq k \leq 75$），分别表示第一棵树的顶点数、第二棵树的顶点数和环的长度。随后有 $n_1 - 1$ 行描述第一棵树，每行包含两个整数 $v_i, u_i$（$1 \leq v_i, u_i \leq n_1$），表示第一棵树的边。再随后有 $n_2 - 1$ 行，以相同格式描述第二棵树。保证给定的图均为树。
## Output
请输出一个整数——环的数量对 $998244353$ 取模的结果。
[samples]
## Note
下图展示了示例测试中树的乘积图。在第一个例子中，长度为 $2$ 的环列表如下：«AB»、«BA»、«BC»、«CB»、«AD»、«DA»、«CD»、«DC»
**Definitions**
Let $ T_1 = (V, E_1) $ and $ T_2 = (U, F) $ be two trees, where $ |V| = n_1 $, $ |U| = n_2 $.
The Cartesian product $ G = T_1 \times T_2 $ is the graph with vertex set $ V \times U $, and edge set defined as:
$$
\{ ((v_1, u), (v_2, u)) \mid (v_1, v_2) \in E_1, u \in U \} \cup \{ ((v, u_1), (v, u_2)) \mid (u_1, u_2) \in F, v \in V \}.
$$
**Constraints**
1. $ 2 \le n_1, n_2 \le 4000 $
2. $ 2 \le k \le 75 $
3. $ T_1 $ and $ T_2 $ are trees (connected, acyclic, undirected).
**Objective**
Compute the number of cycles of length $ k $ in $ G = T_1 \times T_2 $, where a cycle is a sequence $ w_1, w_2, \dots, w_k \in V \times U $ such that:
- $ w_i $ is adjacent to $ w_{i+1} $ for all $ i = 1, \dots, k-1 $,
- $ w_k $ is adjacent to $ w_1 $,
- Cycles differing by cyclic shift or reversal are counted as distinct.
Output the result modulo $ 998244353 $.
API Response (JSON)
{
"problem": {
"name": "D. Cycles in product",
"description": {
"content": "Consider a tree (that is, an undirected connected graph without loops) $T_1$ and a tree $T_2$. Let's define their _cartesian product_ $T_1 \\times T_2$ in a following way. Let $V$ be the set of vertic",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 7000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF997D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Consider a tree (that is, an undirected connected graph without loops) $T_1$ and a tree $T_2$. Let's define their _cartesian product_ $T_1 \\times T_2$ in a following way.\n\nLet $V$ be the set of vertic...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "考虑一棵树（即无环的无向连通图）$T_1$ 和一棵树 $T_2$。我们如下定义它们的 _笛卡尔积_ $T_1 \\times T_2$。\n\n设 $V$ 为 $T_1$ 的顶点集，$U$ 为 $T_2$ 的顶点集。\n\n则图 $T_1 \\times T_2$ 的顶点集为 $V \\times U$，即由有序顶点对组成的集合，其中每对的第一个顶点来自 $V$，第二个来自 $U$。\n\n我们添加如下边：\n\n请参...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ T_1 = (V, E_1) $ and $ T_2 = (U, F) $ be two trees, where $ |V| = n_1 $, $ |U| = n_2 $. \nThe Cartesian product $ G = T_1 \\times T_2 $ is the graph with vertex set $ V \\times U...",
"is_translate": false,
"language": "Formal"
}
]
}