G. Подсчет множества префиксных максимумов
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Определим для массива $$$b$$$ функцию $$$f$$$ такую, что $$$f(b)$$$ возвращает массив префиксных максимумов $$$b$$$. Другими словами, $$$f(b)$$$ — это массив, содержащий только такие элементы $$$b_i$$$, для которых $$$b_i=\max(b_1,b_2,\ldots,b_i)$$$, без изменения их порядка. Например, $$$f([3,10,4,10,15,1])=[3,10,10,15]$$$.

Вам дано дерево, состоящее из $$$n$$$ вершин с корнем $$$1$$$.

Перестановка$$$^\dagger$$$ $$$p$$$ является прямым обходом дерева, если для всех $$$i$$$ выполняется следующее условие:

  • Пусть $$$k$$$ — число потомков$$$^\ddagger$$$ вершины $$$p_i$$$.
  • Для всех $$$x$$$ таких, что $$$i < x \leq i+k$$$, $$$p_x$$$ — потомок вершины $$$p_i$$$.

Найдите количество различных значений $$$f(a)$$$ среди всех возможных прямых обходов $$$a$$$. Так как это значение может быть большим, вам нужно найти его по модулю $$$998\,244\,353$$$.

$$$^\dagger$$$ Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

$$$^\ddagger$$$ Вершина $$$t$$$ является потомком вершины $$$s$$$, если $$$s \neq t$$$ и $$$s$$$ находится на единственном простом пути из $$$t$$$ в $$$1$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — количество вершин.

Следующие $$$n-1$$$ строк содержат по два целых числа $$$u$$$ и $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$), обозначающие ребро между вершинами $$$u$$$ и $$$v$$$. Гарантируется, что заданные ребра образуют дерево.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

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

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

Пример
Входные данные
6
1
2
1 2
3
1 2
1 3
3
1 2
2 3
5
1 2
1 3
1 4
1 5
10
1 2
2 3
1 4
2 5
2 6
4 7
5 8
4 9
9 10
Выходные данные
1
1
2
1
8
6
Примечание

В первом наборе входных данных единственным допустимым прямым обходом является $$$a=[1]$$$. Поэтому единственное возможное значение $$$f(a)$$$ — $$$[1]$$$.

Во втором наборе входных данных единственным допустимым прямым обходом является $$$a=[1,2]$$$. Поэтому единственное возможное значение $$$f(a)$$$ — $$$[1,2]$$$.

В третьем наборе входных данных два допустимых прямых обхода — $$$a=[1,2,3]$$$ и $$$a=[1,3,2]$$$. Таким образом, возможные значения $$$f(a)$$$ — $$$[1,2,3]$$$ и $$$[1,3]$$$.

В пятом наборе входных данных возможными значениями $$$f(a)$$$ являются:

  • $$$[1,5]$$$;
  • $$$[1,2,5]$$$;
  • $$$[1,3,5]$$$;
  • $$$[1,4,5]$$$;
  • $$$[1,2,3,5]$$$;
  • $$$[1,2,4,5]$$$;
  • $$$[1,3,4,5]$$$;
  • $$$[1,2,3,4,5]$$$.