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

Определим уникальную орнаментальную раскраску корневого дерева$$$^{\text{∗}}$$$ как следующую раскраску вершин:

  • Вершина $$$v$$$ окрашивается в белый цвет, если количество вершин в поддереве$$$^{\text{†}}$$$, корнем которого является $$$v$$$, четное;
  • В противном случае $$$v$$$ окрашивается в черный цвет.

На своем пути к завоеванию леса рождественских деревьев Юуки столкнулся с орнаментально окрашенным деревом $$$T$$$ с $$$n$$$ вершинами, пронумерованными от $$$1$$$ до $$$n$$$, корнем которого является вершина $$$1$$$.

Юуки считает дерево завоёванным, если и только если выполняется по крайней мере одно из следующих условий:

  • В дереве нет белых вершин, или
  • Существует такая вершина $$$v$$$, что все белые вершины находятся на простом пути от корня $$$1$$$ до $$$v$$$.

Чтобы завоевать дерево, Юуки может совершить следующую операцию над $$$T$$$ произвольное количество раз (возможно, ноль):

  • Сначала выберите вершину $$$w$$$, которая окрашена в белый цвет и не является корнем $$$T$$$. Пусть $$$p_w$$$ будет родителем $$$w$$$.
  • Затем удалите ребро, соединяющее $$$p_w$$$ и $$$w$$$, и добавьте ребро между любыми двумя вершинами так, чтобы $$$T$$$ оставалось деревом.
  • После этого перекрасьте вершины $$$T$$$ так, чтобы оно было орнаментально окрашено. Обратите внимание, что $$$T$$$ всегда имеет корень в вершине $$$1$$$.
Возможное применение операции в первом наборе входных данных. Получившееся дерево завоевано, так как все белые вершины находятся на пути между вершинами $$$1$$$ и $$$3$$$.

Вам необходимо вычислить количество различных$$$^{\text{‡}}$$$ завоеванных деревьев, которые Юуки может построить, применяя вышеуказанную операцию произвольное количество раз к $$$T$$$. Поскольку ответ может быть большим, выведите его по модулю $$$998\,244\,353$$$.

Обратите внимание, что Юуки не может остановиться на полпути операции (в частности, он должен перекрасить дерево перед тем, как проверить, является ли оно завоеванным). Кроме того, Юуки может применять операцию, даже если дерево уже завоевано.

$$$^{\text{∗}}$$$Деревом называется связный граф без циклов.

$$$^{\text{†}}$$$Поддеревом вершины $$$v$$$ называется подграф, состоящий из вершины $$$v$$$, всех ее потомков, и всех ребер между ними.

$$$^{\text{‡}}$$$Два дерева считаются различными, если и только если существует пара вершин, такая что между ними есть ребро в одном из деревьев, а в другом нет.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — количество вершин в $$$T$$$.

Затем следуют $$$n-1$$$ строк, $$$i$$$-я строка содержит два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1\le u_i \lt v_i\le n$$$) — две вершины, которые соединяет $$$i$$$-е ребро.

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

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

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

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

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

В первом наборе входных данных приведены четыре завоеванных дерева, которые можно построить, и последовательность операций, которые строят каждое из них.

Объяснение
Иллюстрация
  • Операция применяется ноль раз.
  • Данное дерево уже завоевано, так как все белые вершины находятся на простом пути между вершинами $$$1$$$ и $$$4$$$.
  • Первая и единственная операция выбирает $$$w$$$ как вершину $$$3$$$ ($$$p_w$$$ — вершина $$$1$$$) и проводит ребро между вершинами $$$2$$$ и $$$4$$$.
  • Получившееся дерево завоевано, так как все белые вершины находятся на простом пути между вершинами $$$1$$$ и $$$3$$$.
  • Первая и единственная операция выбирает $$$w$$$ как вершину $$$3$$$ ($$$p_w$$$ — вершина $$$1$$$) и проводит ребро между вершинами $$$2$$$ и $$$3$$$.
  • Получившееся дерево завоевано, так как все белые вершины находятся на простом пути между вершинами $$$1$$$ и $$$3$$$.
  • Первая операция выбирает $$$w$$$ как вершину $$$3$$$ ($$$p_w$$$ — вершина $$$1$$$) и проводит ребро между вершинами $$$2$$$ и $$$4$$$.
  • Вторая операция выбирает $$$w$$$ как вершину $$$4$$$ ($$$p_w$$$ — вершина $$$2$$$) и проводит ребро между вершинами $$$1$$$ и $$$4$$$.
  • Получившееся дерево завоевано, так как все белые вершины находятся на простом пути между вершинами $$$1$$$ и $$$4$$$.

Во втором наборе входных данных Юуки не может применить операцию к $$$T$$$, так как белых вершин нет. Кроме того, $$$T$$$ уже завоевано, так как белых вершин нет. Таким образом, ответ равен $$$1$$$.