Description

山海经学院陷入了异端分子的围攻之中，为了防止学院被攻陷，山海经学院的门主$Kisaki$必须要尽快将刚拟定的作战信息传达给每一名位于前线的指挥官。由于通讯被敌方干扰，每位知晓作战信息的指挥官每个单位时间只能将作战信息传达给一名自己的直属长官或直属下属，如：$A$是$B$的直属长官，$B$是$C$的直属长官，那么$A$只能将信息传递给$B$，$B$可以将信息传递给$A$或$C$，$C$只能将信息传递给$B$。

现在，$Kisaki$想要知道，将作战信息传递给所有的指挥官最少需要花费多少单位时间。

$Note$：$Kisaki$作为山海经学院的门主，自然是所有指挥官中级别最高的，且一开始只有$Kisaki$一人知晓作战信息。显然，山海经学院的从属关系网中并不存在环型关系，如：不存在$A$是$B$的长官，$B$是$C$的长官，同时$C$又是$A$的长官这种情况。此外，由于学院人数有限，山海经学院的从属关系深度并不会超过$10^4$层。

Input Format

第一行输入一个正整数$T(1≤T≤10)$，表示共有$T$组测试样例。

对于每组测试样例：

第一行输入一个正整数$n(1≤n≤10^5)$，表示山海经学院共有$n$个指挥官。

接下来第二到第$n$行，描述了山海经学院的从属关系网。每行输入两个正整数$u，v(1≤u,v≤n)$，表示$u$是$v$的直属长官，同时$v$也是$u$的直属下属。在这张关系网中，我们用正整数$1$来代表$Kisaki$。

Output Format

对于每一组测试样例，输出一行，包含一个正整数，表示所需的最短时间。

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

3

Hint

下图展示了一种最优的传递方案，其中红色数字表示已经知晓作战信息的指挥官，黑色数字表示尚未知晓作战信息的指挥官。

Source

1816 Online Judge 10.100.0.232