Problem Description

Given an unrooted tree with $n$ nodes. We want to build bus routes between some pairs of nodes so that between any two nodes, it takes at most two bus routes to travel.

Formally, consider all $\frac{n (n - 1)}{2}$ simple paths on the tree whose endpoints are different. For a subset $S$ of these paths, we call it good if and only if:

• Consider a new graph $G$. For a pair of nodes $u, v$, if and only if there exists a path $P$ in $S$ such that both $u$ and $v$ lie on $P$, we add an undirected edge of weight $1$ between $u$ and $v$.
• Require that the distance between any two nodes in $G$ is at most $2$.

You need to compute how many subsets $S$ are good. Since the answer may be large, output it modulo $998244353$.

Input Format

The first line contains a positive integer $n$, the number of nodes.
The next $n - 1$ lines each contain two positive integers $u, v$, representing a tree edge $(u, v)$.

Output Format

Output one integer, the answer modulo $998244353$.

3
1 2
2 3

5

6
1 2
2 3
2 4
3 5
3 6

27296

Hint

[Sample #1 Explanation]

For the first sample, all feasible plans are $\{(1, 3)\}, \{(1, 3), (1, 2)\}, \{(1, 3), (2, 3)\}, \{(1, 3), (1, 2), (2, 3)\}, \{(1, 2), (2, 3)\}$.

[Sample #3]

See the attachments bus/bus3.in and bus/bus3.ans.

This sample satisfies the constraints of testdata $11 \sim 14$.

[Sample #4]

See the attachments bus/bus4.in and bus/bus4.ans.

This sample satisfies the constraints of testdata $19 \sim 20$.

[Constraints]

For all testdata, it is guaranteed that $1 \le n \le 3000$.

Details are as follows:

Special property A: the tree is a chain.

Translated by ChatGPT 5