С неба упало дерево с $$$n$$$ вершинами, а также изначально пустое множество $$$S$$$. В восторге от этого маловероятного события, вы выполняете следующие действия ровно $$$n - 1$$$ раз:
- пусть $$$x$$$ — лист дерева с максимальным индексом;
- добавьте $$$x$$$ в множество $$$S$$$ (обратите внимание, что если $$$x$$$ уже находится в $$$S$$$, то ничего не меняется);
- выберите любой лист, отличный от $$$x$$$, и удалите его из дерева.
Определите количество различных множеств $$$S$$$, которые вы можете получить. Поскольку это число может быть очень большим, выведите его по модулю $$$998\,244\,353$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — размер дерева.
Затем следуют $$$n - 1$$$ строк, каждая из которых содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u,v \le n, u \ne v$$$), описывающих пару вершин, соединенных ребром. Гарантируется, что заданный граф является деревом.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Выведите количество различных множеств, которые можно получить, по модулю $$$998\,244\,353$$$.
621 255 15 35 45 277 67 45 71 62 43 51010 910 810 710 69 58 47 36 25 142 43 11 441 42 33 4
1131311
Для первого набора входных данных существует только один возможный порядок: $$$1$$$, образующий множество $$$\{2\}$$$.
Для третьего набора входных данных дерево выглядит следующим образом:
Вы можете получить следующие множества:
- $$$\{3, 6, 7\}$$$, удаляя в порядке $$$1, 2, 3, 4, 5, 6$$$
- $$$\{3, 4, 6, 7\}$$$, удаляя в порядке $$$2, 1, 3, 4, 5, 6$$$
- $$$\{3, 4, 5, 6, 7\}$$$, удаляя в порядке $$$2, 3, 1, 4, 5, 6$$$
Можно доказать, что это единственные множества, которые возможно получить.
