E. Ранг случайного леса
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Определим ранг неориентированного графа как ранг его матрицы смежности в $$$\mathbb{R}^{n \times n}$$$.

Дано дерево. Каждое из рёбер дерева исчезает с вероятностью $$$1/2$$$ независимо от остальных. Пусть $$$E$$$ — математическое ожидание ранга полученного леса. Найдите остаток от деления $$$E \cdot 2^{n-1}$$$ на $$$998244353$$$ (несложно показать, что $$$E \cdot 2^{n-1}$$$ — целое число).

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

В первой строке записано одно число $$$n$$$ ($$$1 \le n \le 5 \cdot 10^{5}$$$) — количество вершин дерева.

В следующих $$$n-1$$$ строках описаны рёбра дерева. Каждое ребро описывается парой $$$u$$$ $$$v$$$ ($$$1 \le u, \,\, v \le n; \,\, u \ne v$$$) вершин, которые оно соединяет.

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

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

Выведите одно число — ответ на задачу.

Примеры
Входные данные
3
1 2
2 3
Выходные данные
6
Входные данные
4
1 2
1 3
1 4
Выходные данные
14
Входные данные
4
1 2
2 3
3 4
Выходные данные
18