题目描述

As a member of The Academy of Chtholly, you want to rush to the battle field to help Chtholly.

There are $n$ islands in the sky, and you are in island number $1$.

At first, there are $n-1$ transportation lines, each connecting two islands, making each two islands reachable.

However, due to the continues attack of the beasts on the ground, each transportation line has $50\%$ possibility of being destroyed.

You want to find, in all $2^{n-1}$ possible realities (each transportation line may be destroyed or not), how many of them you can reach exactly $k$ islands. The answer may be large, so you just need to output the answer mod $1811939329$.

输入格式

The input contains multiple test cases.

The first line contains a number $T$ ($1 \le T \le 20$) denoting the number of test cases.

In each test case:

The first line contains a number $n$ ($1 \le n \le 10^5$).

The following $n-1$ lines each contains two numbers $x$, $y$ denoting that there is an edge between $x$ and $y$.

输出格式

For each test case, output one line containing $n$ numbers.

The $k$-th number is the number of possible realities that you can reach exactly $k$ islands.

1
5
1 2
2 3
3 4
4 5

8 4 2 1 1