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

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

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

1. 初始时位于 1 号节点；

2. 如果当前位于叶子节点，则停下并在该节点等待其他操作；

3. 如果当前不是叶子节点，则在其所有儿子中选择一个，使得以该儿子为根的子树中拥有的游客数最少。若多个儿子的子树游客数相同，则选择编号最小的儿子；

4. 移动到选中的儿子节点，继续执行第 2 步。

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

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

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

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

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

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

样例解释

树的结构如下：

        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 位。

数据范围

2026年常州“信息与未来”小学生编程比赛线上

市赛常州2026