Rikka with Tree Game

게임 이론은 컴퓨터 과학의 중요한 분야다. 컴퓨터 과학을 전공하는 대학생에게 게임을 하는 일이 항상 즐거운 과정은 아닐 수 있다.

오늘 Rikka는 트리를 사용한 단순하지만 흥미로운 게임을 연구한다.

루트가 있는 트리 $T$를 생각하자. 처음에는 루트에 토큰이 하나 있다. 두 플레이어가 이 트리에서 번갈아 토큰을 움직이며 게임을 한다. 각 차례에 토큰이 정점 $i$에 있다면, 플레이어는 $i$의 자식 $j$를 하나 골라 토큰을 $j$로 옮긴다. $i$에 자식이 없으면 게임은 즉시 끝난다.

게임의 최종 점수는 토큰이 멈춘 최종 위치의 깊이다. 루트의 깊이는 $1$이고, 나머지 정점의 깊이는 부모의 깊이에 $1$을 더한 값이다. 선공 플레이어는 점수를 최대화하려 하고, 후공 플레이어는 점수를 최소화하려 한다. 두 플레이어 모두 최적으로 플레이한다고 가정한다.

루트가 있는 트리 $T$가 주어졌을 때 게임의 최종 점수를 계산하는 것은 간단한 일이다. 그래서 Rikka는 더 어려운 문제를 풀려고 한다. 그녀는 트리에 몇 가지 연산을 할 수 있다. 매번 트리의 리프 $i$(리프는 자식이 없는 정점이다)를 하나 골라, 정점 $i$를 부모로 하는 새 노드를 트리에 연결한다.

$f(k)$를 두 플레이어가 최적으로 플레이할 때 게임의 최종 점수가 정확히 $k$가 되도록 하는 최소 연산 횟수라고 하자. 불가능하면 $f(k)$를 $-1$이라고 하자. Rikka는 $\lim\limits_{k \rightarrow +\infty}\frac{f(k)}{k}$의 값을 알고 싶어 한다.

Rikka는 질문을 잘하지만 답을 잘하지는 못한다. 그래서 그녀는 당신에게 도움을 청한다.

첫 번째 줄에는 정수 $t$ ($1 \leq t \leq 10^3$)가 주어진다. 이는 테스트 케이스의 수다.

각 테스트 케이스의 첫 번째 줄에는 정수 $n$ ($1 \leq n \leq 10^5$)이 주어진다.

그다음 $n - 1$개의 줄이 주어진다. 각 줄에는 트리의 간선 $(u, v)$를 나타내는 두 정수 $u$와 $v$ ($1 \leq u, v \leq n$)가 주어진다. 루트의 번호는 $1$이다.

주어지는 그래프는 트리임이 보장된다. 또한 $n > 1000$인 테스트 케이스는 최대 $10$개임이 보장된다.

각 테스트 케이스마다 Rikka가 알고 싶어 하는 극한값을 한 줄에 정수 하나로 출력한다. (답이 존재하면 그 값은 정수임이 밝혀져 있다.) 극한이 존재하지 않으면 대신 $-1$을 출력한다.