该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

公园选址

问题描述

红梅公园的地图形如一个 $n$ 个节点构成的有根树，节点编号为 $1 \sim n$。其中，$1$ 号节点是公园入口（也是树的根），而每一个景点都对应一个叶子节点。

作为听松楼新店长的 Childer 想要选择一个人流量适中的地方作为新店铺位置。他计划观测并统计一天内每个叶子节点的游客人数。

在观测的这一天中，将有 $m$ 个游客依次进入公园。游客会优先选择人流量小的地方参观。具体地，对于每位游客，会重复执行如下过程：

1. 初始时位于 $1$ 号节点；
2. 如果当前位于叶子节点，则停下并在该节点等待其他操作；
3. 如果当前不是叶子节点，则在其所有儿子中选择一个，使得以该儿子为根的子树中拥有的游客数最少。若多个儿子的子树游客数相同，则选择编号最小的儿子；
4. 移动到选中的儿子节点，继续执行第 2 步。

只有当前一位游客到达叶子节点停下后，下一位游客才会进入公园。

请求出观测结束后，每个节点的游客数量。注意：所有非叶子节点的游客数量必然为 0。

输入格式

第一行两个正整数 $n, m$，分别表示节点数量和游客总数。

接下来 $n-1$ 行，每行两个正整数 $u, v$，表示 $u$ 和 $v$ 之间有一条边相连。

保证：$2 \le n \le 10^6$，$1 \le m \le 10^{18}$，$1 \le u, v \le n$，且给出的边构成一棵树。

输出格式

输出一行 $n$ 个整数，分别表示每个节点的游客数量。

样例

10 10
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10

0 0 0 0 0 3 2 2 1 2

样例解释

树的结构如下：

        1 (入口)
       / 
      2   3
     / \ / 
    4  5 6  7
   / \ |
  8  9 10

其中叶子节点为 $6, 7, 8, 9, 10$。

$10$ 位游客依次进入，最终分配到各叶子节点的数量为：节点 $6$ 有 $3$ 位，节点 $7$ 有 $2$ 位，节点 $8$ 有 $2$ 位，节点 $9$ 有 $1$ 位，节点 $10$ 有 $2$ 位。

数据范围