猫和老鼠在一棵有 $N$ 个顶点的无向树上玩游戏，顶点编号从 $1$ 到 $N$。猫最初位于顶点 $1$，老鼠位于顶点 $M$。树的每条边都有一个唯一的奶酪数量（从 $1$ 到 $N-1$）。猫和老鼠轮流移动，老鼠先走。在老鼠的回合，它会从当前顶点移动到相邻顶点，选择的是连接当前顶点且奶酪数量最大的边。如果猫位于老鼠选择的那个顶点，老鼠则会移动到第二好的相邻顶点（即连接当前顶点且奶酪数量第二大的边）。如果没有第二个可移动的顶点，则游戏结束，猫获胜。在猫的回合，猫可以移动到任何相邻顶点，也可以留在当前顶点。

你控制猫，目标是尽快赢得游戏。请找出在猫采取最优策略的情况下，老鼠在猫获胜前移动的最少步数。

输入格式

输入文件的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。 每个测试用例的第一行包含 $N$ 和 $M$。接下来的 $N-1$ 行，每行包含两个数字 $u$ 和 $v$，表示顶点 $u$ 和 $v$ 之间有一条边。这些边中的第 $k$ 条（$1 \le k \le N-1$）的奶酪数量等于 $k$。

输出格式

对于每个测试用例，按照输入顺序，输出一行，包含猫获胜前老鼠移动的最少步数（假设猫采取最优策略）。如果猫无法赢得游戏，则输出 $-1$。

数据范围

• $2 \le N \le 50000$
• $1 \le T \le 100$
• $1 \le u, v \le N$
• 每个测试用例给出的图都是一棵树。
• 边上的奶酪不会被老鼠吃掉。因此，在整个游戏过程中，一条边的奶酪数量始终保持不变。
• 猫可以移动到与老鼠相同的顶点。这种移动不会伤害老鼠，游戏正常继续。

样例

样例输入 1

3
10 10
6 7
6 5
5 4
4 1
1 2
1 3
7 8
8 9
9 10
10 6
6 7
6 5
5 4
4 1
1 2
1 3
7 8
8 9
9 10
13 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
5 4
4 3
3 1
1 2

样例输出 1

6
4
4