在美丽的中山纪念中学里面，有一座高一学堂。所谓山不在高，有仙则名；水不在深，有龙则灵。高一学堂，因为有了yxr，就成了现在这个样子 = =。

由于yxr的语言太过雷人，每次他发微往往都会有一石激起千层浪的效果，具体就是所有关注他的人都会转发，同时@他，接着关注这些人的人也会转发，同时@他关注的人（注意转发内容本身会有@yxr），以此类推。这样导致每次yxr发微博都会被@上兆次，而yxr又特别喜欢发，sina 支持不了如此庞大的数据量，特出规定，每次转发时，@的人不能超过 KK 人，好友在转发时如果超过了，就把最早那人删掉。现在yxr刚发了一条微博“求满分”，他想知道每个与他有联系的人分别会被@多少次。

输入第一行有三个整数 N,KN,K，表示人数和KK。

接下来 N-1N−1 行，每行有 22 个整数 a,ba,b，表示 aa 和 bb 有关注关系。

输入给出一棵以 11 号点为根的树，一号点代表yxr，对于任意一个点，他的儿子都关注他。

输出有 NN 行，每行有一个整数，这个人会被@多少次。

样例输入

5 2

1 2

2 3

2 4

4 5

样例输出

3

3

0

1

0

对于 30\%30% 的数据，N≤100N≤100;
对于 60\%60% 的数据，N≤100000,k≤100N≤100000,k≤100； 对于 100\%100% 的数据，N≤100000N≤100000。