题目描述

Prof. Pang and Prof. Shou like playing a chase game.

The game map consists of $n$ rooms and $n-1$ bi-directional channels. The game map is connected. That means, the map forms a tree.

At first, Prof. Pang is in room $u$, while Prof. Shou is in room $v$ ($u\neq v$). Prof. Pang and Prof. Shou take turns to play, and Prof. Shou goes first. In one's turn, the player knows his own position and the other player's position and can decide either to stay in the current room or to move to another room which is connected with the current room directly by a channel. When Prof. Pang and Prof. Shou are in the same room, Prof. Shou is caught by Prof. Pang.

Prof. Pang and Prof. Shou are smart enough. Prof. Pang wants to catch Prof. Shou in a finite number of turns. Prof. Shou does not want to be caught by Prof. Pang in any finite number of turns.

Prof. Shou gets tired of being caught every time and finds Prof. Fei for help. Prof. Shou asks Prof. Fei to add some channels so that Prof. Pang cannot catch him in finite number of turns for any pair of initial rooms $(u,v)$. Prof. Fei is lazy, so he hopes to add as few channels as possible. If no matter how to add the channels there is always a pair of rooms $(u,v)$ such that Prof. Pang can catch Prof. Shou, output $-1$.

输入格式

The first line contains a single integer $T$ ($1\le T\le 10^4$) denoting the number of test cases.

For each test case, the first line contains a single integer $n$ ($2\le n\le 10^5$) denoting the number of rooms.

For the next $n-1$ lines, each line contains two integers $u$ and $v$ ($1\le u, v\le n$) denoting a channel connecting room $u$ and room $v$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\times 10^5$, and the rooms and channels always form a tree.

输出格式

For each test case, print a number denoting the smallest number of added channels, or just print $-1$.

题目大意

【题目描述】

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

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

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

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

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

【输入格式】

第一行包含一个整数 $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$。

【输出格式】

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

翻译来自于：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