Проф. Пан и проф. Шо любят играть в догонялки.
Игровая карта состоит из $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$.
Примеры
Входные данные 1
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 -1 2