Определим ранг неориентированного графа как ранг его матрицы смежности в \(\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
3000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач