G. Gery's Problem and Orz Pandas
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Gery got "Compilation Error" because he forgot to include the C++ standard header cstring. So he lost all the score of three problems. One of the problems is:

There is a tree with $$$n$$$ verticies. $$$m$$$ queries would be performed on it. Each query contains two parameters $$$u$$$ and $$$v$$$. You should calculate $$$$$$\sum_{r=1}^n d_r(u, v)$$$$$$

$$$d_r(u, v)$$$ is the beautifulness of the road from vertex $$$u$$$ to vertex $$$v$$$ in the tree, with vertex $$$r$$$ as the root.

With vertex $$$r$$$ as the root, the beautifulness of the road from $$$u$$$ to $$$v$$$ is defined

$$$$$$d_r(u, v) = dis(u,lca_r(u,v)) \times dis(v,lca_r(u,v))$$$$$$

$$$dis(u,v)$$$ is the direct distance between $$$u$$$ and $$$v$$$, and $$$lca_r(u, v)$$$ is the least common ancestor of $$$u$$$ and $$$v$$$, with $$$r$$$ as the root.

Originally the constraint of this problem was $$$1 \leq n, m \leq 1000$$$. But Gery was in a bad mood so he fortified the problem. The constraint is now $$$1 \leq n, m \leq 10^5$$$.

Help the Orz Pandas to solve this problem so they would be able to access https://gery.top.

Input

There is only one test case in the input file.

The first line contains two integers $$$n$$$ and $$$m$$$ . The $$$i$$$-th of the following $$$n-1$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$, the vertices connected by the $$$i$$$-th edge. Each of the following $$$m$$$ lines contains a pair of integers, $$$u$$$ and $$$v$$$, the pair of vertices being queried.

It's guaranteed that $$$1 \leq n, m \leq 10^5$$$, and $$$1 \leq x_i, y_i, u, v \leq n$$$.

Output

For each query, output one line containing the answer of the query, modulo $$$998244353$$$.

Example
Input
5 2
1 2
1 3
3 4
3 5
4 5
2 5
Output
3
6
Note

For the second query, we have $$$d_1 (2, 5) = dis(2, 1) \times dis(5, 1) = 2$$$, $$$d_2 (2, 5) = dis(2, 2) \times dis(5, 2) = 0$$$, $$$d_3 (2, 5) = dis(2, 3) \times dis(5, 3) = 2$$$, $$$d_4(2, 5) = dis(2, 3) \times dis(5, 3) = 2$$$, and $$$d_5(2, 5) = dis(2, 5) \times dis(5, 5) = 0$$$. Their sum is $$$6$$$.