题目描述

作为 珂朵莉学院 的一员，你想奔赴战场去帮助珂朵莉。

天空中有 $n$ 座岛屿，你位于岛屿 $1$ 号。

初始时，存在 $n-1$ 条交通线，每条连接两座岛屿，使得任意两座岛屿之间均可互相到达。

然而，由于地面上野兽的不断攻击，每条交通线都有 $50\%$ 的概率被摧毁。

你想知道，在全部 $2^{n-1}$ 种可能的现实情况（每条交通线可能被摧毁或保留）中，有多少种现实能使你恰好到达 $k$ 座岛屿。答案可能很大，因此你只需要输出答案对 $1811939329$ 取模的结果。

输入格式

输入包含多组测试数据。

第一行包含一个整数 $T$（$1 \le T \le 20$），表示测试数据的组数。

对于每组测试数据：

第一行包含一个整数 $n$（$1 \le n \le 10^5$）。

接下来的 $n-1$ 行，每行包含两个整数 $x$ 和 $y$，表示 $x$ 与 $y$ 之间有一条边。

输出格式

对于每组测试数据，输出一行共 $n$ 个整数。

第 $k$ 个数表示能够恰好到达 $k$ 座岛屿的可能现实情况的数量。

1
5
1 2
2 3
3 4
4 5

8 4 2 1 1

提示

翻译由 DeepSeek V4 Pro 完成