E. Контроль случайности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево с $$$n$$$ вершинами.

В некоторую вершину $$$v \ne 1$$$ посадят робота. Пусть у вас изначально есть $$$p$$$ монет. Рассмотрим следующий процесс, где в $$$i$$$-й шаг (начиная с $$$i = 1$$$):

  • Если $$$i$$$ нечётное, робот передвинется в соседнюю вершину в сторону вершины $$$1$$$;
  • Иначе, $$$i$$$ чётное. Можно либо заплатить одну монету (если остались), после чего робот передвинется в соседнюю вершину в сторону вершины $$$1$$$, либо ничего не платить, после чего робот передвинется в равновероятно выбранную соседнюю вершину.

Процесс останавливается, как только робот попадает в вершину $$$1$$$. Определим $$$f(v, p)$$$ как минимально возможное математическое ожидание количества шагов процесса выше (количество использованных монет минимизировать не надо).

Необходимо ответить на $$$q$$$ запросов, в $$$i$$$-м из которых надо найти значение $$$f(v_i, p_i)$$$ по модулю$$$^{\text{∗}}$$$ $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$ Формально, пусть $$$M = 998\,244\,353$$$. Можно показать, что ответ может быть представлен в виде несократимой дроби $$$\frac{p}{q}$$$, где $$$p$$$ и $$$q$$$ — целые числа, и $$$q \not \equiv 0 \pmod{M}$$$. Выведите целое число, равное $$$p \cdot q^{-1} \bmod M$$$. Другими словами, выведите такое целое число $$$x$$$, что $$$0 \le x < M$$$ и $$$x \cdot q \equiv p \pmod{M}$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$ строках каждого набора входных данных заданы ребра дерева: по одному в строке. В $$$i$$$-й строке заданы два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \neq v_i$$$), обозначающих ребро между вершинами $$$u_i$$$ и $$$v_i$$$.

В следующих $$$q$$$ строках каждого набора входных данных заданы два целых числа: $$$v_i$$$ и $$$p_i$$$ ($$$2 \le v_i \le n$$$; $$$0 \le p_i \le n$$$).

Гарантируется, что заданные ребра образуют дерево.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10 ^ 3$$$.

Гарантируется, что сумма значений $$$q$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10 ^ 3$$$.

Выходные данные

Для каждого набора входных данных выведите $$$q$$$ целых чисел: значения $$$f(v_i, p_i)$$$ по модулю $$$998\,244\,353$$$.

Формально, пусть $$$M = 998\,244\,353$$$. Можно показать, что ответ может быть представлен в виде несократимой дроби $$$\frac{p}{q}$$$, где $$$p$$$ и $$$q$$$ — целые числа, и $$$q \not \equiv 0 \pmod{M}$$$. Выведите целое число, равное $$$p \cdot q^{-1} \bmod 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$$$ и завершает перемещение.

Посчитаем значение математического ожидания для второго запроса ($$$x$$$ это количество шагов в процессе):

  • $$$P(x < 2) = 0$$$, расстояние до вершины $$$1$$$ равно $$$2$$$ и робот не может дойти до него за меньшее количество шагов.
  • $$$P(x = 2) = \frac{1}{3}$$$, так как есть только одна последовательность шагов, приводящая к $$$x = 2$$$. Это $$$3 \rightarrow_{1} 2 \rightarrow_{0.33} 1$$$ с вероятностью $$$1 \cdot \frac{1}{3}$$$.
  • $$$P(x \bmod 2 = 1) = 0$$$, так как робот может достичь вершину $$$1$$$ сделав только чётное количество шагов.
  • $$$P(x = 4) = \frac{2}{9}$$$: возможные пути $$$3 \rightarrow_{1} 2 \rightarrow_{0.67} [3, 4] \rightarrow_{1} 2 \rightarrow_{0.33} 1$$$.
  • $$$P(x = 6) = \frac{4}{27}$$$: возможные пути $$$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}$$$ в общем случае.

В результате $$$f(v, p) = \sum\limits_{i=1}^{\infty}{i \cdot 2 \cdot \frac{2^{i - 1}}{3^i}} = 6$$$.

Дерево из второго набора показано ниже: