题目描述

译自 ROI Regional 2024 Day1 T4. Выбор столицы

给定一个无向树，即一个包含 $n$ 个顶点且无环的连通图，以及一个整数 $k$。固定树中的某个顶点 $s$ 并将其称为首都。

将树的边从首都开始定向。换句话说，如果将树悬挂在顶点 $s$ 上，如果顶点 $u$ 是顶点 $v$ 的父节点，则将边 $(u, v)$ 定向为 $u \to v$。注意，这样定向后，每个顶点都可以从首都到达。

定义到顶点 $v$ 的距离为从 $s$ 到 $v$ 的最小边数。称顶点 $s$ 的 可达性 为到所有顶点的最大距离。

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

对于树中的每个顶点 $s$，确定如果选择顶点 $s$ 作为首都，添加不超过 $k$ 条额外的有向边，可以达到的最小 可达性。

注意，在某些子任务中，只需要输出第一个顶点的答案。

输入格式

第一行包含三个整数 $n,k,t$ $(2 \le n \le 2 \cdot 10^5, 1 \le k \le n - 1, n \cdot k \le 2 \cdot 10^5, 0 \le t \le 1)$，分别表示树的顶点数、最多添加的边数限制和一个标志 $t$，如果 $t = 0$，则只需要输出编号为 $1$ 的顶点的答案，否则输出所有顶点的答案。

接下来的 $n - 1$ 行中，每行包含两个整数 $u_i$ 和 $v_i$ $(1 \le u_i, v_i \le n)$，表示树的边。

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

输出格式

如果 $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

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

数据范围与提示

详细子任务附加限制及分值如下表所示。