Мяу-мяу! - 1

Ограничение времени1 секунда
Ограничение памяти256 Мб
Вводстандартный ввод
Выводстандартный вывод

В этой задаче на проверку необходимо сдать исходный код программы.

Мурмурградск — город котиков! И, как и во всех таких городах, в Мурмурградске у каждого котика есть собственный дом, а у каждого домика — уникальный номер. Котики не любят мочить лапки, поэтому некоторые дома соединены специальными котодорожками, полностью защищенными от воды.

Многолетние исследования показали следующие примечательные черты Мурмурградска:

1. Дома и котодорожки представляют собой дерево, где дома — вершины, а котодорожки — ребра.

2. Между двумя домами есть котодорожка тогда и только тогда, когда котики в этих домах дружат.

Кошачий мэр решил, что для развития общей сплоченности каким-то котикам нужно будет поменять место жительства. При этом мэру важно, чтобы у всех оставалось свое личное пространство, поэтому никакие два котика не должны жить в одном доме после переезда. Мэр также понял, что, во избежание всеобщего хаоса, надо добавить в план немного стабильности: жители домика номер 1 1 должны остаться на месте.

Но и у котиков тоже есть свои требования, так как они не любят сильно менять обстановку. Им крайне важно, чтобы после переселения в другой домик они смогли добраться до всех своих друзей, пройдя не более чем одну котодорожку.

У мэра слишком много дел, поэтому за помощью он обратился к вам! Он поставил перед вами следующую задачу: посчитать, сколько существует планов переезда, удовлетворяющих и критериям мэра, и критериям населения.

Так как это число может быть очень большим, необходимо посчитать его по модулю 998244353 998244353 .

Формат ввода

В первой строке записано одно целое число t t  — количество наборов входных данных. Далее следуют t t наборов входных данных.

Каждый набор данных состоит из нескольких строк. Первая строка набора данных содержит одно целое число n n  — количество вершин в дереве. Далее идут n 1 n - 1 строк, каждая содержит два целых числа u u и v v ( 1 u , v n 1 \leq u, v \leq n , u v u \neq v ) — две вершины, которые соединены ребром.

Гарантируется, что заданный граф является деревом, в нем отсутствуют петли и кратные ребра.

Формат вывода

Для каждого набора входных данных выведите в отдельной строке одно целое число — количество подходящих планов переезда по модулю 998244353 998244353 .

Система оценивания

Оценка за эту задачу — 50 50 баллов, тестирование проводится онлайн (после тура баллы за задачу не изменятся).

За каждый тест, для которого был найден правильный ответ, начисляется 1 1 балл.

Тесты Дополнительные ограничения
2-4 t t n n дополнительно
1 20 1 - 20 t = 1 t = 1 n 9 n \le 9
21 35 21 - 35 t = 1 t = 1 n 15 n \le 15 Количество подходящих планов переезда не превосходит 1 0 5 10^5
36 50 36 - 50 t = 1 t = 1 n 25 n \le 25 Количество подходящих планов переезда не превосходит 1 0 5 10^5

Пример

ВводВывод
1
6
5 2
1 3
5 4
1 5
1 6
4