题目描述

Crash 小朋友最近迷上了一款游戏——文明5 (Civilization V)。在这个游戏中，玩家可以建立和发展自己的国家，通过外交和别的国家交流，或是通过战争征服别的国家。

现在 Crash 已经拥有了一个 $n$ 个城市的国家，这些城市之间通过道路相连。由于建设道路是有花费的，因此 Crash 只修建了 $n-1$ 条道路连接这些城市，不过可以保证任意两个城市都有路径相通。

在游戏中，Crash 需要选择一个城市作为他的国家的首都，选择首都需要考虑很多指标，有一个指标是这样的：

其中 $S(i)$ 表示第 $i$ 个城市的指标值，${\rm dist}(i, j)$ 表示第 $i$ 个城市到第 $j$ 个城市需要经过的道路条数的最小值，$k$ 为一个常数且为正整数。

因此 Crash 交给你一个简单的任务：给出城市之间的道路，对于每个城市，输出这个城市的指标值，由于指标值可能会很大，所以你只需要输出这个数 $\bmod\ 10007$ 的值。

输入格式

输入的第一行包括两个正整数 $n$ 和 $k$。

接下来有 $n-1$ 行，每行两个正整数 $u, v$（$1\le u, v\le n$），表示第 $u$ 个城市和第 $v$ 个城市之间有道路相连。这些道路保证能符合题目的要求。

输出格式

输出共 $n$ 行，每行一个正整数，第 $i$ 行的正整数表示第 $i$ 个城市的指标值 $\bmod\ 10007$ 的值。

5 2
1 2
1 3
2 4
2 5

10
7
23
18
18

提示

对于 $20 \%$ 的数据，$n\le 5000$，$k\le 30$。

对于 $50 \%$ 的数据，$n\le 5\times 10^4$，$k\le 30$。

对于 $100 \%$ 的数据，$1\le n\le 5\times 10^4$，$1\le k\le 150$。