问题陈述

有一棵树，树上有 $N$ 个顶点，编号为 $1, 2, \ldots, N$ 。对于每个 $i$ ( $1 \leq i \leq N - 1$ )， 第 $i$ 条边连接顶点 $x_i$ 和 $y_i$ 。

太郎决定将每个顶点涂成白色或黑色，并要求任何一个黑色顶点都可以从任何其他黑色顶点通过黑色顶点到达。

给你一个正整数 $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$ ( $1 \leq v \leq N$ ) 行应包含以下问题的答案：

• 假设顶点 $v$ 必须是黑色的，求顶点涂色的方式数，模数为 $M$ 。

3 100
1 2
2 3

3
4
3

如下图所示，顶点有七种涂色方式。其中，顶点 $1$ 为黑色的方式有 3 种，顶点 $2$ 为黑色的方式有 4 种，顶点 $3$ 为黑色的方式有 3 种。

4 100
1 2
1 3
1 4

8
5
5
5

1 100

1

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

0
0
1
1
1
0
1
0
1
1

请务必打印答案的模数 $M$ 。

来源

https://atcoder.jp/contests/dp/tasks/dp_v