#C. 小 D 不是 OP!

    Type: Default File IO: genshin 1000ms 512MiB

小 D 不是 OP!

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

小 D 不是 OP!(genshin)

众所周知,小 D 不是 OP,所以小 I 在玩原神的时候只会跑图开宝箱。

原神地图可以视作为 mm 个国家,每个国家 ii 包含个 kik_i 城市,一个国家之间通过 ki1k_i-1 条道路把所有城市相连,不同国家的城市之间没有道路。

小 I 一开始在 11 号国家的城市 11。小 I 想要经过 k1+k2++kmk_1+k_2+\dots+k_m 时刻之后遍历所有国家的所有城市再回到起点。小 I 可以通过花费 11 时刻从 uu 到达 vv 当且仅当:u,vu,v 通过道路相连,或者 u,vu,v 处于不同国家(这样小 ii 就会使用传送锚点)。

你需要告诉小 I 他有多少种方案遍历所有城市。答案对 998244353998244353 取模。

输入格式

第一行一个正整数 mm 表示国家数目。

对于每个国家,第一行一个 kik_i 表示城市数目。

接下来 ki1k_i-1 行,每行两个正整数 uj,vju_j,v_j 描述一条这个国家的道路(uj,vj[1,ki]u_j,v_j\in[1,k_i])。

输出格式

对每个测试点输出一个正整数表示答案。

测试样例

样例输入 样例输出
2121 2 2
见下发 genshin/genshin2.in\textit{genshin/genshin2.in} 见下发 genshin/genshin2.ans\textit{genshin/genshin2.ans}
见下发 genshin/genshin3.in\textit{genshin/genshin3.in} 见下发 genshin/genshin3.ans\textit{genshin/genshin3.ans}
见下发 genshin/genshin4.in\textit{genshin/genshin4.in} 见下发 genshin/genshin4.ans\textit{genshin/genshin4.ans}

样例解释

假设 (x,y)(x,y) 表示第 xx 个国家的第 yy 个城市。那么样例 11 有两种方案:

(1,1)(2,1)(2,2)(1,1)(1,1)\to (2,1)\to(2,2)\to (1,1)(1,1)(2,2)(2,1)(1,1)(1,1)\to(2,2)\to(2,1)\to(1,1)

样例 22 满足测试点 11 的限制。

样例 33 满足测试点 7,147,14 的限制。

样例 44 满足测试点 1515 的限制。

数据范围

对所有数据,有 m300,ki5000m\leq 300,\sum k_i\leq 5000

测试点编号 ki\sum k_i\leq mm\leq kik_i\leq 国家道路的形态
11 1010 33 1010
22 1515 44
33 600600 300300 22
464\sim 6 900900 33
7107\sim 10 25002500 5050
111411\sim 14 50005000 300300 50005000 每个国家道路都是链
152015\sim 20

时间限制:1s\tt 1s

空间限制:512MB\tt 512MB

Odoo 省选模拟赛

Not Attended
Status
Done
Rule
OI
Problem
3
Start at
2024-2-29 8:00
End at
2024-2-29 12:00
Duration
4 hour(s)
Host
Partic.
4