Rikka with Tree Game

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

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

Given a rooted tree $T$, at first, there is a token on the root. Two players play games on this tree using the token alternately. In each turn, assume the token's position is $i$, the player needs to choose a child $j$ of $i$ and move the token to $j$. If $i$ has no child, the game will end 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 first player wants to maximize the score while the second player wants to minimize the score. Assume both of the two players play optimally.

Given the rooted tree $T$, calculating the final score of the game is a simple task. So Rikka wants to solve a more challenging task. She can do some operations to the tree, each time, she can choose a $leaf$ $i$ from the tree (i.e. the chosen node mustn't have any children) and link a new node to the tree with node $i$ as its father.

Let $f(k)$ be the minimum number of operations to make the game's final score be exactly $k$. If it is impossible, $f(k)$ will be $-1$. And Rikka wants to know $\lim_{k \rightarrow +\infty}\frac{f(k)}{k}$.

You know, Rikka is a good questioner, but not a good task solver. So, she asks you for some help.

The first line contains a single number $t(1\leq t \leq 10^3)$.

For each testcase, the first line contains two numbers $n(1\leq n \leq 10^5)$.

Then $n-1$ lines follow, each line contains two integers $u,v(1 \leq u,v \leq n)$ which describes the tree. The index of the root is $1$.

The input guarantees that there are at most $10$ testcases with $n > 1000$.

For each query, output a single line with a single number, the answer. If the limit does not exist, output $-1$.

1
8
1 2
2 3
2 4
4 5
4 8
5 6
5 7

2

寒武纪ACM金牌训练营-重现赛