题目描述

等到一切有关这【】OI 的事情结束，所有的利益与竞争化为乌有，我们还会是朋友……吗？

小 $\sigma$ 有一张包含 $n$ 个人，$n-1$ 条朋友关系的关系网。保证在这个关系网中所有人连通，也就是说，将 $n$ 个人视为点，$n-1$ 条朋友关系视为边后该关系网为一棵树。

关系网是会变化的，毕竟没有永远的朋友。

小 $\sigma$ 常常追忆过去，他想起过去的关系网是现在关系网按 $1,2,3, \ldots, n$ 顺序加入点后的重构树。

小 $\sigma$ 常常幻想未来，他发现未来的关系网是现在关系网按 $n, n-1, n-2, \ldots, 1$ 顺序加入点后的重构树。

小 $\sigma$ 定义，对于某两张关系网而言，如果 $\{1,2,3, \ldots, n\}$ 的一个非空集合 $S$ 在两张关系网上的导出子图均为一个连通块，则 $S$ 为这两张关系网的不变朋友子集。

小 $\sigma$ 想知道，过去的关系网与现在的关系网有多少不变朋友子集以及过去的关系网与未来的关系网有多少不变朋友子集。由于答案可能较大，你只需要输出答案对 $998244353$ 取模后的值即可。

形式化题意

给定一棵 $n$ 个点的树 $T$ ，定义 $T_{\max }$ 为按 $1,2,3, \ldots, n$ 顺序加入点后的重构树，$T_{\min }$ 为按 $n, n-1, n-2, \ldots, 1$ 顺序加入点后的重构树，$f\left(T_1, T_2\right)$ 为使得 $S$ 在 $T_1, T_2$ 上的导出子图均为连通块的 $\{1,2,3, \ldots, n\}$ 的非空子集 $S$ 个数。求 $f\left(T_{\max }, T\right)$ 与 $f\left(T_{\max }, T_{\min }\right)$ 对 $998244353$ 取模后的值。

按顺序 $ord_1, ord_2, ord_3, \ldots, ord_n$ 加入点构建重构树的具体流程为：

1. 维护点集 $S$ ，按 $i=1,2,3, \ldots, n$ 依次遍历每个 $p=o r d_i$ 。
2. 对于所有在原树上与 $p$ 相邻且在 $S$ 中的点 $q$ ，将 $S$ 点集的导出子图中 $q$ 所在连通块最晚加入 $S$ 的点在重构树上与 $p$ 连边。
3. 将 $p$ 加入点集 $S$ 。

输入格式

第一行两个正整数 $tp, n$ ，分别表示询问类型与点数。$tp=1$ 时你需要输出过去的关系网与现在的关系网有多少不变朋友子集，$tp=2$ 时你需要输出过去的关系网与未来的关系网有多少不变朋友子集。

接下来 $n-1$ 行，每行两个正整数 $u_i, v_i$ ，表示一条朋友关系。保证在这个关系网中所有人连通。

输出格式

一行，输出一个非负整数，表示答案对 $998244353$ 取模后的值。

1 6
3 1
1 6
6 4
4 2
4 5

15

2 6
3 1
1 6
6 4
4 2
4 5

13

数据范围

对于所有数据： $1 \leq t p \leq 2,1 \leq n \leq 2 \times 10^5$ ，保证关系网中所有人连通。