题目描述

给定一棵包含 $n$ 个节点的无根树，节点编号为 $1\sim n$。

对于一个非空节点集合 $S$，如果由 $S$ 中所有节点以及它们之间原有的树边构成的子图连通，则称 $S$ 是一个连通点集。

接下来有 $m$ 次询问。每次给出两个节点 $u,v$，请计算同时包含 $u$ 和 $v$ 的连通点集数量。

当 $u=v$ 时，只要求所选连通点集包含节点 $u$。

答案对 $998244353$ 取模。

输入格式

在文件 connect.in 中读入。

第一行两个整数 $n,m$，分别表示节点数量和询问数量。

接下来 $n-1$ 行，每行两个整数 $a_i,b_i$，表示树上的一条边。

接下来 $m$ 行，每行两个整数 $u_i,v_i$，描述一次询问。

输出格式

在文件 connect.out 中输出。

对于每次询问输出一行，表示同时包含 $u_i,v_i$ 的连通点集数量对 $998244353$ 取模后的结果。

样例

样例输入 #1

10 10
2 1
3 1
4 3
5 4
6 5
7 6
8 7
9 4
10 4
9 2
5 6
9 8
3 8
3 2
5 7
4 10
3 7
7 9
4 6

样例输出 #1

10
51
8
12
21
34
40
24
16
48

样例输入 #2

36 1
1 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
2 17
2 18
2 19
2 20
2 21
2 22
2 23
2 24
2 25
2 26
26 27
26 28
28 29
28 30
30 31
30 32
30 33
33 34
33 35
35 36
1 1

样例输出 #2

0

样例 2 解释

实际方案数不为 $0$，但其对 $998244353$ 取模后的结果为 $0$。

数据范围

本题共 $20$ 个测试点，每点 $5$ 分。

对于全部数据，$1\le n,m\le5\times10^5$，$1\le u_i,v_i\le n$，输入的 $n-1$ 条边保证构成一棵树。

其他限制

• 时间限制：$2\text{ s}$；
• 空间限制：$512\text{ MiB}$。