На відстані

Limits: 2 sec., 256 MiB

Зеник із Марічкою мають дерево із $n$ вершин, а також натуральне число $k$. Вершини дерева пронумеровані цілими числами від 1 до $n$ включно.

Вони хочуть для кожної вершини $i$ ($1 \le i \le n$) дізнатись, скільки вершин знаходяться на відстані рівно $k$ від неї. Відстань між двома вершинами дерева це найменша кількість ребер, які знаходяться на шляху між цими вершинами.

Допоможіть їм знайти те, що вони шукають.

Input

У першому рядку задано два цілих числа $n$ та $k$ — кількість вершин та відстань, відповідно.

У наступних $n-1$ рядках задано пари цілих чисел $u_i$ та $v_i$, розділених пробілами — ребра дерева.

Output

Виведіть $n$ цілих чисел через пробіл, $i$-те з яких — кількість вершин на відстані $k$ від $i$.

Constraints

$1 \le n, k \le 2 \cdot 10^5$,

$1 \le u_i, v_i \le n$,

Заданий граф є деревом.

Samples

Input (stdin) сopy	Output (stdout) сopy
7 1 2 1 3 2 3 7 4 1 1 5 1 6	4 2 2 1 1 1 1

Input (stdin) сopy	Output (stdout) сopy
7 3 2 1 3 2 3 7 4 1 1 5 1 6	1 0 3 1 1 1 1