#P9982. 天天爱跑步

天天爱跑步

天天爱跑步

Problem Description

PESTC 为了监控同学们的课外运动量,开发了一款名为「天天爱跑步」的 APP。PESTC 的地图可以抽象为一个由 nn 个点与 nn 条边组成的无向连通图,并且图中无重边和自环(也就是一棵基环树)。 学校要求每名同学都要进行 nn 天打卡,对于第 ii 天,为了监控学生的跑步路线,APP 会自动规划地图上一条经过点 ii 的最长简单路径作为今天的跑步路线。现在你想知道每天的跑步路线有多长。 一条路径的长度定义为这条路径上包含的边的条数。

Input

第一行一个正整数 TT(1≤T≤3001\le T\le 300),表示数据组数。 对于每组数据,第一行一个正整数 nn(3≤n≤1053\le n\le 10^5),表示地图上的点数。 接下来 nn 行每行两个整数 u,vu,v(1≤u,v≤n1\le u,v\le n,u≠vu\neq v),表示有一条连接 u,vu,v 两个点的无向边。保证给出的图无重边。 保证所有数据的 nn 之和不超过 5×1055\times 10^5。

Output

对于每组数据,输出一行 nn 个整数,第 ii 个整数表示第 ii 天规划的跑步路线长度。

Sample Input

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

Sample Output

4 4 4 4 4
4 4 4 3 4 4

Source

2024“钉耙编程”中国大学生算法设计超级联赛(6)