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$