Description

有一棵树有 $N$ 个顶点，编号为 $1,2,…,N$。对于 $i(1≤i≤N−1)$ ，第 $i$ 条边连接 $x_i$ 顶点​和 $y_i$​.

光头强决定将每个顶点涂成白色或黑色，并且，所有黑色顶点都仅通过黑色顶点连通。

给你一个正整数 $M$。

对于每个 $v(1≤v≤N)$ ，回答以下问题：

• 假设顶点 $v$ 必须是黑色的，求出可以绘制顶点的方式的数量，模 $M$。

Input

输入格式如下：

$N\ M\\x_1​\ y_1\\​x_2​\ y_2​\\:\\x_{N−1}​\ y_{N−1}​$​

输入中的所有值都是整数。

$1≤N≤10^5\\2≤M≤10^9\\1≤x_i​,y_i​≤N$。

给定的图形是一棵树。

Output

输出 $N$ 行。第 $v(1≤v≤N)$ 行应包含以下问题的答案：

假设顶点 $v$ 必须是黑色的，求出可以绘制顶点的方式的数量，模 $M$。

Samples

3 100
1 2
2 3

3
4
3

有七种方法可以绘制顶点，如下图所示。其中，顶点1为黑色的方式有三种，顶点2为黑色的四种，顶点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$ 的结果。