题目描述

对于树 $T(V, E)$ 和 $S ⊆ V$，记 $f(S, T)$ 表示 $T$ 的对 $S$ 的导出子图（即仅保留 $S$ 中的点和两端都在 $S$ 中的边得到的图）中度数小于等于 $1$ 的点的数量。

对于两棵树 $T_1(V_1, E_1), T_2(V_2, E_2)$，若 $V_1 = V_2$，我们称 $T_1 ≼ T_2$ 当且仅当对于任意 $S_2 ⊆ V_2$，存在 $S_1$ 满足 $S_2 ⊆ S_1 ⊆ V_1$ 且 $f(S_1, T_1) ≤ f(S_2, T_2)$。

称 $T_1, T_2$ 等价当 $T_1 ≼ T_2$ 且 $T_2 ≼ T_1$，记作 $T_1 ∼ T_2$。该等价关系将 $n$ 个点的有标号树划分成若干等价类。

问：

1. 给定 $k$ 棵 $n$ 个点的树 $T_1, T_2 \dots , T_k$，求满足 $T ≼ T_i, ∀1 ≤ i ≤ k$ 的有标号树 $T$ 构成的等价类数量。

2. 给定 $k$ 棵 $n$ 个点的树 $T_1, T_2 \dots , T_k$，求满足 $T_i ≼ T, ∀1 ≤ i ≤ k$ 的有标号树 $T$ 数量。

注意两问的计数对象不同。两问答案均对 $998, 244, 353$ 取模。

保证答案取模后非 $0$。

输入格式

从标准输入读入数据。

输入第一行一个整数 $p$，其中 $p ∈ \{0, 1\}$，$p = 0$ 表示询问第一问，否则表示询问第二问。

接下来一行两个正整数 $k, n$，分别表示输入树的数量以及点数。

接下来依次输入 $k$ 棵树，对于每棵树输入 $n - 1$ 行每行两个正整数 $u, v$ 描述树中的一条边。

输出格式

输出到标准输出。

输出一行一个整数表示答案对 $998, 244, 353$ 取模后的结果。

0
1 4
1 2
1 3
1 4

2

1
1 4
1 2
2 3
3 4

16

提示

【样例 1 解释】

可以证明 $4$ 个点的有标号树被划分成了 $5$ 个等价类，所有的链在同一个等价类，而其它分别以每个点为菊花中心对应一个等价类。

可以验证链对应的等价类和该树本身所在的等价类均满足要求，而其他等价类不满足要求。

【样例 2 解释】

可以验证所有 $4$ 个点的有标号树共 $16$ 个均满足要求。

【样例 3 ~ 10】

见题目目录下的 3.in ~ 10.in 与 3.ans ~ 10.ans。

【子任务】

对于所有数据，保证 $p ∈ \{0, 1\}$，$3 ≤ n ≤ 5000$，$1 ≤ k ≤ 1000$，$1 ≤ u, v ≤ n$，答案取模后不等于 $0$。

子任务编号	$p$	$n$	$k$	树形态	分数
$1$	$\in\{0,1\}$	$\le8$	$\le4$	无特殊形态	$10$
$2$	$=0$	$\le200$	$\le1$	菊花	$4$
$3$				无特殊形态	$8$
$4$			$\le2$		$9$
$5$			$\le40$		$10$
$6$		$\le5000$	$\le10^3$		$14$
$7$	$=1$	$\le200$	$\le1$	链	$7$
$8$				无特殊形态
$9$			$\le2$		$10$
$10$			$\le40$
$11$		$\le5000$	$\le10^3$		$11$

“树形态”中，“菊花”指存在一个向所有点有直接连边的点，“链”指所有点度数不超过 $2$。