Counting Stickmen

Namesolo has fallen in love with the game Stick Fight. But when he is playing the game, he wonders how to find out the number of stickmen in the game.



In this question, we define the stick man as shown in the picture above. It has a chain of length $1$ as the head, two chains of length $2$ as the arms, a chain of length $1$ as the body, and two chains of length $1$ as the legs. For example, the red part in this picture can be viewed as a stick man, with chain $(2,3)$ to be the head, chains $(3,4,6)$ and $(3,9,10)$ to be the arms, chain $(3,5)$ to be the body, and chains $(5,7)$ and $(5,8)$ to be the legs.

The game can be viewed as a tree, and Namesolo wants to know how many stickmen are there. Please note that two stickmen are different when there is at least one different edge between the two edge sets that make up the two stickmen.

Because the answer may be too large, Namesolo wants to know the answer modulo $998244353$.

The first line of input contains one integer $T\ (1\le T\le 15)$, indicating the number of test cases.

For each test case, the first line contains an integer $n$ ($1\le n \le 5\times 10^5$), indicating the number of vertices in the tree. Each of the following $n-1$ lines contains two integers $a,b$ ($1 \le a,b \le n$), indicating that there is an edge connecting $a$ and $b$ in the tree.

It is guaranteed that the sum of $n$ over all cases won't exceed $3 \times 10^6$.

For each test case, output an integer representing the answer modulo $998244353$.

1
9
1 2
2 3
3 4
2 5
5 6
2 7
7 8
7 9

1

2022“杭电杯”中国大学生算法设计超级联赛（7）