Prof. Pang et Prof. Shou aiment jouer à un jeu de poursuite.

La carte du jeu se compose de $n$ salles et $n - 1$ canaux bidirectionnels. La carte du jeu est connexe. Cela signifie que la carte forme un arbre.

Au début, Prof. Pang est dans la salle $u$, tandis que Prof. Shou est dans la salle $v$ ($u \neq v$). Prof. Pang et Prof. Shou jouent à tour de rôle, et Prof. Shou commence. À son tour, le joueur connaît sa propre position ainsi que celle de l'autre joueur et peut décider soit de rester dans la salle actuelle, soit de se déplacer vers une autre salle directement reliée à la salle actuelle par un canal. Lorsque Prof. Pang et Prof. Shou se trouvent dans la même salle, Prof. Shou est attrapé par Prof. Pang.

Prof. Pang et Prof. Shou sont suffisamment intelligents. Prof. Pang veut attraper Prof. Shou en un nombre fini de tours. Prof. Shou ne veut pas être attrapé par Prof. Pang en un nombre fini de tours.

Prof. Shou, fatigué d'être attrapé à chaque fois, demande de l'aide à Prof. Fei. Prof. Shou demande à Prof. Fei d'ajouter des canaux afin que Prof. Pang ne puisse pas l'attraper en un nombre fini de tours, quelle que soit la paire de salles initiales $(u, v)$. Prof. Fei est paresseux, il espère donc ajouter le moins de canaux possible. Si, peu importe la manière d'ajouter les canaux, il existe toujours une paire de salles $(u, v)$ telle que Prof. Pang puisse attraper Prof. Shou, affichez $-1$.

Entrée

La première ligne contient un entier unique $T$ ($1 \le T \le 10^4$) indiquant le nombre de cas de test.

Pour chaque cas de test, la première ligne contient un entier unique $n$ ($2 \le n \le 10^5$) indiquant le nombre de salles.

Pour les $n - 1$ lignes suivantes, chaque ligne contient deux entiers $u$ et $v$ ($1 \le u, v \le n$) indiquant un canal reliant la salle $u$ et la salle $v$.

Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $2 \times 10^5$, et que les salles et les canaux forment toujours un arbre.

Sortie

Pour chaque cas de test, affichez un nombre indiquant le plus petit nombre de canaux à ajouter, ou affichez $-1$.

Exemples

Entrée 1

4
2
1 2

Sortie 1

-1

Entrée 2

4
1 2
2 3
3 4

Sortie 2

1

Entrée 3

4
1 2
2 3
2 4

Sortie 3

-1

Entrée 4

5
1 2
2 3
3 4
3 5

Sortie 4

2