MianKing 有一棵包含 $n$ 个节点的树。他有一个黑棋和一个白棋，初始时两个棋子都在树的某些节点上。

现在 MianKing 将进行以下操作，直到黑棋和白棋位于同一个节点上：如果黑棋在节点 $x$ 上，令 $S$ 为与 $x$ 直接相连的节点集合。然后 MianKing 会从 $S$ 中随机选择一个节点，并将黑棋移动到该节点。

令 $Len$ 表示 MianKing 进行的操作次数，现在令 $f(S, T)$ 表示当黑棋初始在节点 $S$、白棋初始在节点 $T$ 时，$Len^2$ 的期望值。

令 $Sub(x)$ 表示以节点 $1$ 为根时，$x$ 的子树中所有节点的集合。现在 MianKing 想要你回答 $Q$ 个询问，每个询问由两个整数 $A, B$ 组成，你需要计算： $$\sum_{S \in Sub(A)} \sum_{T \in Sub(B)} f(S, T)$$ 题目保证对于每个询问，$Sub(A) \cap Sub(B) = \emptyset$。

如果答案是一个不可约分数 $\frac{x}{y}$，你需要输出一个在 $[0, 998244352]$ 范围内的整数 $d$，满足 $d \times y \pmod{998244353} = x \pmod{998244353}$。题目保证 $y \pmod{998244353} \neq 0$。

输入格式

第一行包含两个整数 $n, Q$。

接下来 $n - 1$ 行，每行包含两个整数 $(x, y)$，表示树的一条边。

接下来 $Q$ 行，第 $i$ 行包含两个整数 $(A, B)$，表示第 $i$ 个询问。

$1 \le n, Q \le 10^5$

题目保证对于每个询问，$Sub(A) \cap Sub(B) = \emptyset$。

输出格式

输出 $Q$ 行，第 $i$ 行包含一个整数，表示对应询问的答案。如果答案是一个不可约分数 $\frac{x}{y}$，你需要输出一个在 $[0, 998244352]$ 范围内的整数 $d$，满足 $d \times y \pmod{998244353} = x \pmod{998244353}$。题目保证 $y \pmod{998244353} \neq 0$。

样例

样例输入 1

3 1
1 2
1 3
2 3

样例输出 1

24

样例输入 2

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

样例输出 2

6508
408
2833
960