问题描述

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

太郎决定将每个顶点涂成白色或黑色，使得从任意一个黑色顶点只经过黑色顶点可以到达任意另一个黑色顶点。

给定一个正整数 $M$。回答以下问题：

• 假设顶点 $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$ 取模。

示例输入 1

3 100
1 2
2 3

示例输出 1

3
4
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$ 取模。