19002번 - Rikka with Tree Game 다국어

문제

Game theory is an important branch of computer science. So, for a college student who is a computer science major, playing games may not always be an enjoyable process.

Today, Rikka is doing some research about a simple but interesting game with trees.

Consider a rooted tree $T$. Initially, there is a token on the root. Two players play a game on this tree, taking turns to move the token. On each turn, assuming the token's position is vertex $i,ドル the player needs to choose a child $j$ of $i$ and move the token to $j$. If $i$ has no child, the game ends immediately.

The final score of the game is the depth of the final position of the token (the depth of the root is 1ドル,ドル and the depth of every other vertex is 1ドル$ plus the depth of its parent). The first player wants to maximize the score, while the second player wants to minimize the score. Assume that both players play optimally.

Given a rooted tree $T,ドル calculating the final score of the game is a simple task. So Rikka wants to solve a more challenging problem. She can do some operations to the tree: each time, she can choose a leaf $i$ of the tree (a leaf is a vertex which does not have any children) and link a new node to the tree with node $i$ as its parent.

Let $f(k)$ be the minimum number of operations to make the game's final score be exactly $k,ドル assuming that both players play optimally. If it is impossible, let $f(k)$ be $-1$. Rikka wants to know the value $\lim\limits_{k \rightarrow +\infty}\frac{f(k)}{k}$.

You know, Rikka is good at asking questions, but not as good at answering them. So, she asks you for help.

입력

The first line contains a single integer $t$ (1ドル \leq t \leq 10^3$), the number of test cases.

For each test case, the first line contains an integer $n$ (1ドル \leq n \leq 10^5$).

Then $n - 1$ lines follow. Each of them contains two integers $u$ and $v$ (1ドル \leq u, v \leq n$) which describe an edge $(u, v)$ of the tree. The index of the root is 1ドル$.

It is guaranteed that the given graphs are trees. It is also guaranteed that there are at most 10ドル$ test cases with $n > 1000$.

출력

For each test case, print a single line with a single integer: the value of the limit Rikka wants to know. (It turns out that, if the answer exists, it is an integer.) If the limit does not exist, print $-1$ instead.

제한

힌트