Problem Description

PESTC 为了监控同学们的课外运动量，开发了一款名为「天天爱跑步」的 APP。PESTC 的地图可以抽象为一个由 $n$ 个点与 $n$ 条边组成的无向连通图，并且图中无重边和自环（也就是一棵基环树）。

学校要求每名同学都要进行 $n$ 天打卡，对于第 $i$ 天，为了监控学生的跑步路线，APP 会自动规划地图上一条经过点 $i$ 的最长简单路径作为今天的跑步路线。现在你想知道每天的跑步路线有多长。

一条路径的长度定义为这条路径上包含的边的条数。

Input

第一行一个正整数 $T$（$1\le T\le 300$），表示数据组数。

对于每组数据，第一行一个正整数 $n$（$3\le n\le 10^5$），表示地图上的点数。

接下来 $n$ 行每行两个整数 $u,v$（$1\le u,v\le n$，$u\neq v$），表示有一条连接 $u,v$ 两个点的无向边。保证给出的图无重边。

保证所有数据的 $n$ 之和不超过 $5\times 10^5$。

Output

对于每组数据，输出一行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 天规划的跑步路线长度。

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

4 4 4 4 4
4 4 4 3 4 4