Different Distances - Repovive Premier Round 2 | Repovive

3E. Different Distances

2500 pts2s256 MB

You are given a tree with $n$ vertices numbered from $1$ to $n$ .

A subset of vertices $S$ is called good if for every two distinct vertices $1 \le v,u \le n$ , there exists a vertex $x \in S$ such that $dist(v,x) \ne dist(u,x)$ .

Compute the number of good subsets $S$ , modulo $998244353$ .

Constraints

$1 \le t \le 10^4$
$3 \le n \le 2 \times 10^5$
The given graph is a tree, it has exactly $n-1$ edges
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \times 10^5$

Input

t \\[0.5em] \left. \begin{array}{l} n \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

Case 2

Case 3

Case 4

Explanation

Case 1

This tree is a simple path $1-2-3-4-5$ . For example, $S=\{2,3\}$ is good, because for any two distinct vertices $u \ne v$ , at least one of $x=2$ or $x=3$ has different distances to them, so $dist(u,x) \ne dist(v,x)$ . On the other hand, $S=\{3\}$ is not good, because vertices $2$ and $4$ have the same distance to $3$ , so $dist(2,3)=dist(4,3)=1$ , and there is no other vertex in $S$ to distinguish them.

Case 2

This tree has a branching at vertex $2$ (edges $1-2$ , $2-3$ , $2-4$ ). For example, $S=\{1,3\}$ is good, since every pair of vertices can be distinguished using either $x=1$ or $x=3$ . However, $S=\{2\}$ is not good, because vertices $1$ and $3$ have the same distance to $2$ , so $dist(1,2)=dist(3,2)=1$ .

Output

Case 1

Case 2

Case 3

Case 4

You are given a tree with $n$ vertices numbered from $1$ to $n$ .

A subset of vertices $S$ is called good if for every two distinct vertices $1 \le v,u \le n$ , there exists a vertex $x \in S$ such that $dist(v,x) \ne dist(u,x)$ .

Compute the number of good subsets $S$ , modulo $998244353$ .

Constraints

$1 \le t \le 10^4$
$3 \le n \le 2 \times 10^5$
The given graph is a tree, it has exactly $n-1$ edges
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \times 10^5$

t \\[0.5em] \left. \begin{array}{l} n \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

3E. Different Distances

Input

Output

Samples

3E. Different Distances

Constraints

Input

Output

Samples

Constraints