У Васи есть дерево из \(n\) вершин. Он хочет знать количество способов удалить некоторое количество ребер (возможно, ни одного) из дерева так, чтоб в оставшемся графе максимальное паросочетание было единственно.
Паросочетанием в графе называется подмножество ребер такое, что все концы этих ребер различны. Максимальным паросочетанием называется такое паросочетание, в котором количество ребер максимально возможное.
Так как количество способов может быть велико, выведите его по модулю \(998244353\).
Выходные данные
В единственной строке выведите число — количество способов удалить ребра в дереве так, чтобы в оставшемся графе максимальное паросочетание было единственно. Выведите ответ по модулю \(998244353\).
Примечание
В первом тестовом примере максимальное паросочетание будет единственно в четырех случаях:
- если удалить ребра \((1, 2)\) и \((1, 3)\).
- если удалить ребра \((1, 2)\) и \((1, 4)\).
- если удалить ребра \((1, 3)\) и \((1, 4)\).
- если удалить все ребра.
Во втором тестовом примере максимальное паросочетание будет единственно в шести случаях:
- если не удалять ни одного ребра.
- если удалить ребра \((1, 2)\) и \((2, 3)\).
- если удалить ребра \((1, 2)\) и \((3, 4)\).
- если удалить ребра \((2, 3)\) и \((3, 4)\).
- если удалить ребро \((2, 3)\).
- если удалить все ребра.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2
1 3
1 4
|
4
|
|
2
|
4
1 2
2 3
3 4
|
6
|
|
3
|
1
|
1
|