На відстані
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) | Output (stdout) |
|---|---|
| 7 1 2 1 3 2 3 7 4 1 1 5 1 6 | 4 2 2 1 1 1 1 |
| Input (stdin) | Output (stdout) |
|---|---|
| 7 3 2 1 3 2 3 7 4 1 1 5 1 6 | 1 0 3 1 1 1 1 |
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|