Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

E. Control of Randomness
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with n vertices.

Let's place a robot in some vertex v≠1, and suppose we initially have p coins. Consider the following process, where in the i-th step (starting from i=1):

  • If i is odd, the robot moves to an adjacent vertex in the direction of vertex 1;
  • Else, i is even. You can either pay one coin (if there are some left) and then the robot moves to an adjacent vertex in the direction of vertex 1, or not pay, and then the robot moves to an adjacent vertex chosen uniformly at random.

The process stops as soon as the robot reaches vertex 1. Let f(v,p) be the minimum possible expected number of steps in the process above if we spend our coins optimally.

Answer q queries, in the i-th of which you have to find the value of f(vi,pi), modulo∗ 998244353.

∗ Formally, let M=998244353. It can be shown that the answer can be expressed as an irreducible fraction pq, where p and q are integers and q \not \equiv 0 \pmod{M}. Output the integer equal to p \cdot q^{-1} \bmod M. In other words, output such an integer x that 0 \le x < M and x \cdot q \equiv p \pmod{M}.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 \le t \le 10^3). The description of the test cases follows.

The first line of each test case contains two integers n and q (2 \le n \le 2 \cdot 10^3; 1 \le q \le 2 \cdot 10^3) — the number of vertices in the tree and the number of queries.

The next n - 1 lines contain the edges of the tree, one edge per line. The i-th line contains two integers u_i and v_i (1 \le u_i, v_i \le n; u_i \neq v_i), denoting the edge between the nodes u_i and v_i.

The next q lines contain two integers v_i and p_i (2 \le v_i \le n; 0 \le p_i \le n).

It's guaranteed that the given edges form a tree.

It is guaranteed that the sum of n over all test cases does not exceed 2 \cdot 10 ^ 3.

It is guaranteed that the sum of q over all test cases does not exceed 2 \cdot 10 ^ 3.

Output

For each test case, print q integers: the values of f(v_i, p_i) modulo 998\,244\,353.

Formally, let M = 998\,244\,353. It can be shown that the answer can be expressed as an irreducible fraction \frac{p}{q}, where p and q are integers and q \not \equiv 0 \pmod{M}. Output the integer equal to p \cdot q^{-1} \bmod M. In other words, output such an integer x that 0 \le x < M and x \cdot q \equiv p \pmod{M}.

Example
Input
2
4 4
1 2
2 3
2 4
2 0
3 0
4 0
3 1
12 10
1 2
2 3
2 4
1 5
5 6
6 7
6 8
6 9
8 10
10 11
10 12
6 0
9 0
10 0
11 0
3 1
7 1
10 1
12 1
12 2
11 12
Output
1
6
6
2
4
9
8
15
2
3
6
9
5
5
Note

The tree in the first test case:

In the first query, the expected value is equal to 1, since the robot starts moving from vertex 2 to vertex 1 in the first step and the process stops.

Let's calculate the expected value in the second query (x is the number of steps):

  • P(x < 2) = 0, the distance to vertex 1 is 2 and the robot cannot reach it in fewer steps.
  • P(x = 2) = \frac{1}{3}, since there is only one sequence of steps leading to x = 2. This is 3 \rightarrow_{1} 2 \rightarrow_{0.33} 1 with probability 1 \cdot \frac{1}{3}.
  • P(x \bmod 2 = 1) = 0, since the robot can reach vertex 1 by only taking an even number of steps.
  • P(x = 4) = \frac{2}{9}: possible paths 3 \rightarrow_{1} 2 \rightarrow_{0.67} [3, 4] \rightarrow_{1} 2 \rightarrow_{0.33} 1.
  • P(x = 6) = \frac{4}{27}: possible paths 3 \rightarrow_{1} 2 \rightarrow_{0.67} [3, 4] \rightarrow_{1} 2 \rightarrow_{0.67} [3, 4] \rightarrow_{1} 2 \rightarrow_{0.33} 1.
  • P(x = i \cdot 2) = \frac{2^{i - 1}}{3^i} in the general case.

As a result, f(v, p) = \sum\limits_{i=1}^{\infty}{i \cdot 2 \cdot \frac{2^{i - 1}}{3^i}} = 6.

The tree in the second test case: