Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

These problems are from the atcoder DP contest, and were transferred onto DMOJ. All problem statements were made by several atcoder users. As there is no access to the test data, all data is randomly generated. If there are issues with the statement or data, please contact Rimuru or Ninjaclasher on slack.

There is a tree with N vertices, numbered 1, 2, \ldots, N. For each i\ (1 \le i \le N-1), the i-th edge connects Vertex x_i and y_i.

Taro has decided to paint each vertex in white or black, so that any black vertex can be reached from any other black vertex by passing through only black vertices.

You are given a positive integer M. For each v\ (1 \le v \le N), answer the following question:

  • Assuming that Vertex v has to be black, find the number of ways in which the vertices can be painted, modulo M.

Constraints

  • All values in input are integers.
  • 1 \le N \le 10^5
  • 2 \le M \le 10^9
  • 1 \le x_i, y_i \le N
  • The given graph is a tree.

Input Specification

The first line will contain two integers N and M.

The next N-1 lines will each contain two integers x_i and y_i.

Output Specification

Print N lines. The v-th (1 \le v \le N) ) line should contain the answer to the following question:

  • Assuming that Vertex v has to be black, find the number of ways in which the vertices can be painted, modulo M.

Sample Input 1

3 100
1 2
2 3

Sample Output 1

3
4
3

Explanation For Sample 1

There are seven ways to paint the vertices, as shown in the figure below. Among them, there are three ways such that Vertex 1 is black, four ways such that Vertex 2 is black and three ways such that Vertex 3 is black.

Sample Input 2

4 100
1 2
1 3
1 4

Sample Output 2

8
5
5
5

Sample Input 3

1 100

Sample Output 3

1

Sample Input 4

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

Sample Output 4

0
0
1
1
1
0
1
0
1
1

Explanation For Sample 4

Be sure to print the answers modulo M.


Comments

There are no comments at the moment.