Description

允许在树中增加不超过 $k$ 条额外的有向边。对于树中的每个节点 $s$，确定如果选择节点 $s$ 作为树根，能够达到的最小可达性是多少。

注意，在某些子任务中，只需要输出顶点编号为 $1$ 的答案。

Input Format

第一行包含三个整数 $n$，$k$ 和 $t$ （$2 \leq n \leq 2 \times 10^5$，$1 \leq k \leq n - 1$，$n \times k \leq 2 \times 10^5$，$0 \leq t \leq 1$），分别表示树的顶点数量、额外添加的有向边的最大数量限制和一个整数 $t$，如果 $t$ 为 $0$，则只需输出顶点编号为 $1$ 的答案；如果 $t$ 为 $1$，则输出所有顶点的答案。

接下来的 $n - 1$ 行每行包含两个整数 $u_i$ 和 $v_i$ （$1 \leq u_i, v_i \leq n$），表示树的一条边。

保证所给的边构成一棵树。

Output Format

如果 $t = 0$，输出一个整数，即选择顶点编号为 $1$ 作为树根，并且增加不超过 $k$ 条额外的有向边时，可以达到的最小可达性。

如果 $t = 1$，输出 $n$ 个数，第 $i$ 个数表示选择顶点 $i$ 作为树根，并且增加不超过 $k$ 条额外的有向边时，可以达到的最小可达性。

5 2 1
1 2
1 3
2 4
2 5

1 1 2 2 2

3 1 0
1 2
2 3

1

Hint

下图给出了第一个样例的图片。虚线表示添加的边。对于顶点 $1$ 和 $2$，最小可达性为 $1$；对于顶点 $3$，$4$ 和 $5$，最小可达性为 $2$。

对于 $100\%$ 的数据，$2 \leq n \leq 2 \times 10^5$，$1 \leq k \leq n - 1$，$n \times k \leq 2 \times 10^5$，$0 \leq t \leq 1$，$1 \leq u_i, v_i \leq n$。