You are given a tree with \(n\) vertices and \(k\) edges. Each edge has a color between 1 and \(k\). For each \(i\), from 1 to \(k\), determine the number of paths \((v,\ u)\) in the tree with \(i\) different colors.

Note: \((v, u) \neq (u, v)\)

Input format

First line: \(n\) and \(k\) 

Next \(n-1\) lines: Each line contains two numbers \(p_i\) and \(c_i\) denoting the parent of \((i + 1)^{th}\) node and the color of the edge connecting \(i + 1\) to \(p_i\).

Output format

Print \(k\) numbers where the \(i^{th}\) number denotes the number of paths containing \(i\) different colors.

Constraints

\(1 \le n \le 10^5\\ 1 \le k \le 5\\ 1 \le p_i < i\)