Bus Routes on a Tree

Given an unrooted tree with n nodes. There are \(\frac{n(n-1)}{2}\) simple paths (each corresponding to the unique simple path between two distinct nodes). We want to choose a subset S of these paths (to build bus routes) such that in the new graph G built as follows, the distance between any two nodes is at most 2.

Graph Construction: For every pair of distinct nodes u and v, add an undirected edge of weight 1 between u and v if and only if there exists a chosen path P in S for which both u and v lie on P (i.e. the bus route passes through both nodes).

Requirement: The resulting graph G must satisfy that the distance (minimum number of edges) between any two nodes is at most 2.

Your task is to compute the number of subsets S that are good (i.e. yield a graph G with diameter at most 2). Since the answer might be huge, output it modulo 998244353.

Note: A useful observation is that \(G\) has diameter at most 2 if and only if there exists at least one node that is adjacent to every other node in \(G\) (i.e. a universal vertex). In other words, the chosen bus routes must guarantee that there is some node v such that for every other node u, there is at least one bus route in S whose corresponding tree path contains both v and u.

This problem may be solved by a careful combinatorial analysis or, if the tree is small, by brute force. For the purposes of this problem, you may assume that n is small (for example, n ≤ 6), so that a brute force over the \(\frac{n(n-1)}{2}\) possible bus routes is feasible.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 6), the number of nodes in the tree. Each of the following n−1 lines contains two integers u and v (1 ≤ u,v ≤ n) indicating an edge between nodes u and v.

outputFormat

Output a single integer: the number of good subsets S modulo 998244353.

sample

2
1 2

1