E2. 距离树（困难版）
每次测试时间限制：2 秒
每次测试内存限制：512 兆字节

本题与前一题的区别仅在于 $n$ 的取值范围。

树是一个无环连通的无向图。带权树的每条边都有一个权值。两点间的距离是连接它们的路径上权值之和的最小值。

给定一棵 $n$ 个顶点的带权树，每条边的权值均为 $1$。记 $d(v)$ 为顶点 $1$ 与顶点 $v$ 之间的距离。

设 $f(x)$ 为：若你可以在任意两个顶点 $a$ 和 $b$（$1 \le a, b \le n$）之间临时添加一条权值为 $x$ 的边（注意：添加后图不再是一棵树），则 $\max_{1 \le v \le n} d(v)$ 可能的最小值。

对于每个整数 $x$ 从 $1$ 到 $n$，求出 $f(x)$。

输入
第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。
每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 3 \cdot 10^5$）。
接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示 $u$ 与 $v$ 之间有一条边。保证这些边构成一棵树。
所有测试用例的 $n$ 之和不超过 $3 \cdot 10^5$。

输出
对于每个测试用例，在一行中输出 $n$ 个整数，其中第 $x$ 个整数等于 $f(x)$。

示例
输入

3
4
1 2
2 3
1 4
2
1 2
7
1 2
1 3
3 4
3 5
3 6
5 7

输出

1 2 2 2 
1 1 
2 2 3 3 3 3 3 

注意

在第一个测试用例中：

• 当 $x = 1$ 时，我们可以在顶点 $1$ 与 $3$ 之间添加一条边，则 $d(1) = 0$，$d(2) = d(3) = d(4) = 1$，所以 $f(1) = 1$。
• 当 $x \ge 2$ 时，无论添加哪条边，都有 $d(1) = 0$，$d(2) = d(4) = 1$，$d(3) = 2$，所以 $f(x) = 2$。