分数: 100 点
问题陈述
有一棵树 N 顶点,编号 1, 2, \ldots, N。 对于每个 i (1 \leq i \leq N - 1), i第一条边连接顶点 x_i 和 y_i.
Taro 决定将每个顶点绘制为白色或黑色,以便从任何其他黑色顶点仅通过黑色顶点即可到达任何黑色顶点。
给你一个正整数 M。 对于每个 v (1 \leq v \leq N),回答以下问题:
- 假设顶点 v 必须是黑色,找到可以绘制顶点的方式的数量,取模 M.
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 10^5
- 2 \leq M \leq 10^9
- 1 \leq x_i, y_i \leq N
- 给定的图是一棵树。
输入
输入由标准输入按以下格式给出:
N M
x_1 y_1
x_2 y_2
:
x_{N - 1} y_{N - 1}
输出
打印 N 行。 的 v-th (1 \leq v \leq N) 行应包含以下问题的答案:
- 假设顶点 v 必须是黑色,找到可以绘制顶点的方式的数量,取模 M.
示例输入 1
3 100 1 2 2 3
示例输出 1
3 4 3
绘制顶点的方法有七种,如下图所示。 其中,Vertex有3种方式 1 是黑色,四种方式使顶点 2 是黑色的,三种方式使得顶点 3 是黑色的。

示例输入 2
4 100 1 2 1 3 1 4
示例输出 2
8 5 5 5
示例输入 3
1 100
示例输出 3
1
示例输入 4
10 2 8 5 10 8 6 5 1 5 4 8 2 10 3 6 9 2 1 7
示例输出 4
0 0 1 1 1 0 1 0 1 1
请务必打印模数答案 M.