{"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 vertices in $T_1$ and $U$ be the set of vertices in $T_2$.\n\nThen 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$.\n\nLet's draw the following edges:\n\n*   Between $(v, u_1)$ and $(v, u_2)$ there is an undirected edge, if $u_1$ and $u_2$ are adjacent in $U$.\n*   Similarly, between $(v_1, u)$ and $(v_2, u)$ there is an undirected edge, if $v_1$ and $v_2$ are adjacent in $V$.\n\nPlease see the notes section for the pictures of products of trees in the sample tests.\n\nLet'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$.\n\nThe 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**.\n\n## Input\n\nFirst 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.\n\nThen 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.\n\nThen follow $n_2 - 1$ lines, which describe the second tree in the same format.\n\nIt is guaranteed, that given graphs are trees.\n\n## Output\n\nPrint one integer — number of cycles modulo $998244353$.\n\n[samples]\n\n## Note\n\nThe following three pictures illustrate graph, which are products of the trees from sample tests.\n\nIn the first example, the list of cycles of length $2$ is as follows:\n\n*   «AB», «BA»\n*   «BC», «CB»\n*   «AD», «DA»\n*   «CD», «DC»\n\n<center>![image](https://espresso.codeforces.com/3331f619f35bbacce43883d747d920cfa72459f4.png) ![image](https://espresso.codeforces.com/59037cc5f09bf73f73a117311ff4330ae41a7860.png) ![image](https://espresso.codeforces.com/cb83a42fc52331266c233dc67312c1f42c04cd9f.png)</center>","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请参见注释部分以查看示例测试中树的乘积图。\n\n现在考察图 $T_1 \\times T_2$。它包含多少个长度为 $k$ 的环（不一定是简单环）？由于这个数可能非常大，请输出对 $998244353$ 取模的结果。\n\n一个顶点序列 $w_1, w_2, \\dots, w_k$，其中 $w_i \\in V \\times U$，被称为环，当且仅当任意相邻顶点均相邻，且 $w_1$ 与 $w_k$ 相邻。仅因循环移位或遍历方向不同而不同的环仍被视为 *不同* 的环。\n\n输入的第一行包含三个整数 $n_1$, $n_2$ 和 $k$（$2 \\leq n_1, n_2 \\leq 4000$，$2 \\leq k \\leq 75$），分别表示第一棵树的顶点数、第二棵树的顶点数和环的长度。\n\n随后有 $n_1 - 1$ 行描述第一棵树，每行包含两个整数 $v_i, u_i$（$1 \\leq v_i, u_i \\leq n_1$），表示第一棵树的边。\n\n再随后有 $n_2 - 1$ 行，以相同格式描述第二棵树。\n\n保证给定的图均为树。\n\n请输出一个整数——环的数量对 $998244353$ 取模的结果。\n\n下图展示了示例测试中树的乘积图。\n\n在第一个例子中，长度为 $2$ 的环列表如下：\n\n## Input\n\n输入的第一行包含三个整数 $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$ 行，以相同格式描述第二棵树。保证给定的图均为树。\n\n## Output\n\n请输出一个整数——环的数量对 $998244353$ 取模的结果。\n\n[samples]\n\n## Note\n\n下图展示了示例测试中树的乘积图。在第一个例子中，长度为 $2$ 的环列表如下：«AB»、«BA»、«BC»、«CB»、«AD»、«DA»、«CD»、«DC»","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 $, and edge set defined as:  \n$$\n\\{ ((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 \\}.\n$$\n\n**Constraints**  \n1. $ 2 \\le n_1, n_2 \\le 4000 $  \n2. $ 2 \\le k \\le 75 $  \n3. $ T_1 $ and $ T_2 $ are trees (connected, acyclic, undirected).  \n\n**Objective**  \nCompute 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:  \n- $ w_i $ is adjacent to $ w_{i+1} $ for all $ i = 1, \\dots, k-1 $,  \n- $ w_k $ is adjacent to $ w_1 $,  \n- Cycles differing by cyclic shift or reversal are counted as distinct.  \n\nOutput the result modulo $ 998244353 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF997D","tags":["combinatorics","divide and conquer","trees"],"sample_group":[["2 2 2\n1 2\n1 2","8"],["2 2 4\n1 2\n1 2","32"],["2 3 4\n1 2\n1 2\n1 3","70"],["4 2 2\n1 2\n1 3\n1 4\n1 2","20"]],"created_at":"2026-03-03 11:00:39"}}