A. Attending Classes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It is a well known fact that people in Switzerland like to go out for walks, and a less known fact is that students at ETH actually attend classes (This may be a myth).

The city of Zurich can be modelled as a graph of $$$n$$$ locations and $$$n-1$$$ bidirectional roads, in which it is possible to travel between any pair of locations using the given roads. We also know that there are $$$q$$$ students that go to ETH, with the $$$i$$$-th student living at location $$$a_i$$$ and having a class today at location $$$b_i$$$.

Now today each student will go out for a random walk as follows. It will start at its home, then choose any adjacent location to its current location with equal probability that they hasn't visited today and walk there. If there exists no such location they will walk the same way back home. If a student ever walks to a location in which they have a class in, they will attend the class.

Our question for you is, what is the probability that the $$$i$$$-th student will attend their own class. It can be shown that this answer can always be expressed as a fraction $$$\frac{1}{p}$$$ where $$$p$$$ is an integer. Output $$$p$$$ modulo $$$998244353$$$.

Input

The first line contains two integers $$$n, q$$$ ($$$2 \leq n \leq 10^5); (1 \leq q \leq 10^5)$$$, the number of locations in Zurich and the number of students attending ETH.

The next $$$n-1$$$ lines contain two integers each $$$u_i, v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$), corresponding to a bidirectional road between location $$$u_i$$$ and $$$v_i$$$.

The next $$$q$$$ lines contain two integers each $$$a_i, b_i$$$ ($$$1 \leq a_i, b_i \leq n)$$$, giving that the $$$i$$$-th student lives at location $$$a_i$$$ and has a class at location $$$b_i$$$, it is guaranteed that $$$a_i \neq b_i$$$.

Output

Output should contains $$$q$$$ lines, for each line print $$$p$$$ modulo $$$998244353$$$ such that the probability of the $$$i$$$-th student attending their class is $$$\frac{1}{p}$$$.

Examples
Input
5 4
1 2
1 3
4 5
1 4
1 5
3 5
3 1
3 2
Output
3
2
1
2
Input
8 5
1 2
2 3
4 5
1 4
6 7
6 8
1 8
4 2
7 8
4 5
6 7
4 1
Output
4
1
2
2
2