题目描述

给定一颗 $n(\le 10^5)$ 个节点的树，第 $i$ 条边连接顶点 $x_i$ 和 $y_i$.

现在 $Bob$ 要将顶点染成白色或黑色，要求任何黑色顶点仅经过黑色顶点到达其他任意黑色顶点(即黑色顶点在树上是连通的)。

你需要帮助 $Bob$ 计算，对于顶点 $v=1 \dots n$, 将顶点 $v$ 染成黑色，有多少种合法的染色方案数？

方案数可能很多，只需要方案数取 $m$ 的余数就可以了。

输入格式

格式如下：

$n$ $m$

$x_1$ $y_1$

$x_2$ $y_2$

$:$

$x_{n - 1}$ $y_{n - 1}$

注意 $m$ 不一定是质数。

输出格式

输出共 $n$ 行

第 $v$ （ $1 \leq v \leq n$ ）行表示将顶点 $v$ 染成黑色合法的方案数取 $m$ 的余数。

3 100
1 2
2 3

3
4
3

样例1解释

总共有 $7$ 种染色方案，如下图：

对于顶点 $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

下发数据：down.zip

数据规模与约定

所有数据满足：

• 输入中的所有值均为整数。

• $1 \leq n \leq 10^5$

• $2 \leq m \leq 10^9$

• $1 \leq x_i, y_i \leq n$

• 保证给定的是一颗树。

$Subtask1$: $n\le 10^3$ , $35$ 分 (下发数据1)

$Subtask2$: $n\le 10^5$ , $m=100000921$(质数)，数据随机， $20$ 分 (下发数据2)

$Subtask3$: 无额外限制， $45$ 分 (下发数据3)