题目描述

给定一棵有 N 个点的树。

你可以执行如下操作：

• 删除任意一条边；
• 再加入另一条边；
• 且操作后的图仍然必须是一棵树。

对于树中的每一个点（编号为 0 到 N-1），你都要计算：最少需要多少次上述操作，才能把它变成这棵树的重心（centroid）。

这里，“某点是树的重心”指的是：若把它作为根，则它每个儿子对应的子树大小都不超过 N/2。

注意，对每一个点的操作序列都必须从原始树开始计算，而不是在别的点调整后的结果上继续操作。

请编写程序 ctree.cpp，它会和评测器一起编译（输入输出由评测器负责），用于解决本题。你的程序必须能够在不重启的情况下处理多个测试。

实现细节

你需要实现如下函数：

std::vector<int> solve(int N, std::vector<int> X, std::vector<int> Y);

该函数会被调用任意多次，并接收：

• 树的点数 N；
• 两个长度均为 N-1 的数组 X 和 Y。

树的边为所有二元组 (X[i], Y[i])，其中 0 ≤ i < N-1。

函数应返回一个长度为 N 的数组，其中第 i 个元素表示：把点 i 变成整棵树的重心所需的最少操作次数。

你的程序：

• 必须实现 solve；
• 不能包含 main 函数；
• 不能从标准输入读入，也不能向标准输出写出；
• 必须包含头文件：

#include "ctree.h"

在满足上述条件的前提下，你可以自由定义辅助函数、全局变量、常量等。

限制

• 1 ≤ S ≤ 3 × 10^5

其中 S 表示单个测试中所有 N 的总和。

本地测试

你会得到文件 ctree.h 和 Lgrader.cpp，可将它们与你的程序一起编译进行测试。

程序启动后：

• 首先输入子测试个数；
• 对于每个子测试：
  • 先输入 N；
  • 接着输入 N-1 行，每行两个整数 X[i] 和 Y[i]；
• 对于每个子测试，程序会输出你的 solve 返回的答案。

子任务

只有当某个子任务中的**所有测试（及其子测试）**全部通过时，才能获得该子任务的分数。

样例

输入

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

输出

0 1 1
1 0 1 2 2 1 1