题目描述

给定一棵 $n$ 个顶点的无向树和一个整数 $k$。

选择树上的某个顶点 $s$ 作为首都。然后将所有树边都按从首都出发的方向定向。也就是说，如果把树以 $s$ 为根，那么每条边都从父亲指向儿子。

此时从首都 $s$ 可以到达所有顶点。定义顶点 $s$ 的可达性为从 $s$ 到所有顶点的最短路长度中的最大值。

现在允许向这棵树中额外添加不超过 $k$ 条有向边。

对于每个顶点 $s$，请计算如果选择 $s$ 作为首都，并额外添加不超过 $k$ 条有向边后，能够达到的最小可达性。

注意：在部分子任务中，只要求输出顶点 $1$ 作为首都时的答案。

输入格式

第一行包含三个整数 $n,k,t$：

• $n$ 表示树的顶点数；
• $k$ 表示最多可以添加的额外有向边数量；
• $t=0$ 表示只需要输出顶点 $1$ 的答案；
• $t=1$ 表示需要输出所有顶点的答案。

接下来 $n-1$ 行，每行包含两个整数 $u_i,v_i$，表示树上的一条无向边。

输出格式

如果 $t=0$，输出一个整数，表示选择顶点 $1$ 作为首都时可以达到的最小可达性。

如果 $t=1$，输出 $n$ 个整数，第 $i$ 个整数表示选择顶点 $i$ 作为首都时可以达到的最小可达性。

数据范围

输入保证给出的边构成一棵树。

子任务

样例

样例 1

5 2 1
1 2
1 3
2 4
2 5

1 1 2 2 2

样例 2

3 1 0
1 2
2 3

1

样例说明