E. 随机性控制
每个测试的时间限制：2 秒
内存限制：256 兆字节

你有一棵包含 $n$ 个顶点的树。

假设我们把机器人放在某个顶点 $v \neq 1$ 上，初始时有 $p$ 枚硬币。考虑以下过程，在第 $i$ 步（从 $i=1$ 开始）：

• 若 $i$ 是奇数，机器人向顶点 $1$ 的方向移动到相邻顶点；
• 若 $i$ 是偶数，你可以选择：
  • 若还有硬币剩余，支付一枚硬币，然后机器人向顶点 $1$ 的方向移动到相邻顶点；
  • 或不支付硬币，则机器人随机均匀地移动到一个相邻顶点。

当机器人到达顶点 $1$ 时，过程结束。
设 $f(v,p)$ 为 最优使用硬币的情况下，上述过程中期望步数的最小可能值。

你需要回答 $q$ 个查询，在第 $i$ 个查询中，求出 $f(v_i, p_i)$ 的值，并对 $998244353$ 取模 $^*$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^3$）。

每个测试用例的描述如下：

• 第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 2 \cdot 10^3$；$1 \le q \le 2 \cdot 10^3$）—— 树的顶点数和查询数。
• 接下来 $n-1$ 行，每行包含一条边 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \neq v_i$）。
• 接下来 $q$ 行，每行包含两个整数 $v_i$ 和 $p_i$（$2 \le v_i \le n$；$0 \le p_i \le n$）。

保证：

• 给定的边构成一棵树。
• 所有测试用例的 $n$ 之和 $\le 2\cdot 10^3$。
• 所有测试用例的 $q$ 之和 $\le 2\cdot 10^3$。

输出

对于每个测试用例，输出 $q$ 个整数：$f(v_i, p_i)$ 对 $998244353$ 取模后的值。

形式化定义：
令 $M = 998244353$。可以证明答案为不可约分数 $\frac{p}{q}$，其中 $p,q$ 为整数且 $q \not\equiv 0 \pmod{M}$。
输出整数 $x$ 满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$。

示例

输入：

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

输出：

1
6
6
2
4
9
8
15
2
3
6
9
5
5

注释

第一个测试用例的树结构：

• 第一个查询：期望值为 $1$，因为机器人从顶点 $2$ 出发，第一步就向顶点 $1$ 移动并结束。
• 第二个查询（$v=3, p=0$）：
  距离顶点 $1$ 为 $2$，机器人不可能在少于 $2$ 步内到达。
  计算得 $f(3,0) = 6$。

第二个测试用例的树结构见题目原图。