У Васи есть дерево из \(n\) вершин. Он хочет знать количество способов удалить некоторое количество ребер (возможно, ни одного) из дерева так, чтоб в оставшемся графе максимальное паросочетание было единственно.
Паросочетанием в графе называется подмножество ребер такое, что все концы этих ребер различны. Максимальным паросочетанием называется такое паросочетание, в котором количество ребер максимально возможное.
Так как количество способов может быть велико, выведите его по модулю \(998244353\).
Первая строка содержит целое число \(n\) (\(1 \le n \le 3 \cdot 10^5\)) – количество вершин дерева.
Следующие \(n − 1\) строк содержат по два числа \(u\) и \(v\) (\(1 \le u, v \le n, u \neq v\)), представляющие ребро между вершинами \(u\) и \(v\). Гарантируется, что данные ребра составляют дерево.
В единственной строке выведите число — количество способов удалить ребра в дереве так, чтобы в оставшемся графе максимальное паросочетание было единственно. Выведите ответ по модулю \(998244353\).
В первом тестовом примере максимальное паросочетание будет единственно в четырех случаях:
Во втором тестовом примере максимальное паросочетание будет единственно в шести случаях:
4 1 2 1 3 1 4
4
4 1 2 2 3 3 4
6
1
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач