Description

庞教授和寿教授喜欢玩追逐游戏。

游戏地图由 $n$ 个房间和 $n-1$ 条双向通道组成。游戏地图是连通的。这意味着地图形成一棵树。

一开始，庞教授在房间 $u$，而寿教授在房间 $v$（$u\neq v$）。庞教授和寿教授轮流玩游戏，寿教授先开始。在自己的回合中，玩家知道自己所在的位置和另一个玩家的位置，可以决定留在当前房间或者移动到与当前房间直接通过通道相连的另一个房间。当庞教授和寿教授在同一个房间时，寿教授被庞教授抓住。

庞教授和寿教授足够聪明。庞教授希望在有限的回合内抓住寿教授。寿教授不希望在任何有限的回合内被庞教授抓住。

寿教授厌倦了每次都被抓住，找到了费教授寻求帮助。寿教授请求费教授添加一些通道，使得无论初始房间对 $(u,v)$ 如何，庞教授都无法在有限的回合内抓住他。费教授很懒，所以他希望尽可能少地添加通道。如果无论如何添加通道，总是存在一对房间 $(u,v)$，使得庞教授能够抓住寿教授，输出 $-1$。

Input Format

第一行包含一个整数 $T$ ($1\le T\le 10^4$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($2\le n\le 10^5$)，表示房间的数量。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$ ($1\le u, v\le n$)，表示连接房间 $u$ 和房间 $v$ 的通道。

保证所有测试用例中 $n$ 的总和不超过 $2\times 10^5$，并且房间和通道始终构成一棵树。

对于每个测试用例，输出一个数字表示添加的通道的最小数量，或者只输出 $-1$。

Output Format

输出一行整数，表示答案。

翻译来自于：ChatGPT

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

-1
1
-1
2