You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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