← 返回题目列表

Codeforces · 917/D

D. 陌生的树

中文机器翻译题面 查看原题

威尔与颠倒怪物有心灵联系,所以怪物知道的一切,威尔都知道。突然,他开始画画,一页又一页,不停歇。乔伊斯、他的妈妈和霍珀酋长把这些图画放在一起,他们意识到,这是一棵贴有标签的树!

树是连通的非循环图。威尔的树有 n 个顶点。乔伊斯和霍珀不知道这意味着什么,所以他们正在调查这棵树和类似的树。对于每个 k,使得 0 ≤ k ≤ n - 1,他们将调查所有具有 n 个顶点且与 Will 的树共享 k 个边的所有标记树。当且仅当存在一对顶点 (v, u),使得一棵树中 v 和 u 之间存在边,而另一棵树中不存在边时,两棵标记树是不同的。

Hopper 和 Joyce 想知道他们需要做多少工作,因此他们要求您告诉他们,对于每个 k,有 n 个顶点且与 Will 的树完全共享 k 个边的标记树的数量。答案可能非常大,所以他们只要求你告诉他们答案模 1000000007 = 109 + 7。

输入

输入的第一行包含一个整数 n (2 ≤ n ≤ 100) — 树的大小。

接下来的 n - 1 行包含 Will 树的边缘。每行包含两个整数 v 和 u (1 ≤ v, u ≤ n, v ≠ u),即边的端点。保证给定的图是一棵树。

输出

在一行中打印 n 个整数。第 i 个整数应该是具有 n 个顶点且与 Will 的树完全共享 i - 1 条边的标记树的数量,模 1000 000 007 = 109 + 7。

示例

输入 #1

3
1 2
1 3

输出 #1

0 2 1

输入 #2

4
1 2
2 3
3 4

输出 #2

1 7 7 1

输入 #3

4
1 2
1 3
1 4

输出 #3

0 9 6 1