eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Время жить

Время жить

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Как Вы знаете, большинство компьютерных сетей имеют древовидную структуру, то есть от каждого и до каждого компьютера можно добраться только по единственному пути.

Так называемый параметр Время Жизни (ВЖ) определяет количество шагов, через которое блуждающий по сети пакет данных уничтожается, если он еще не достиг места назначения. Цель ВЖ состоит в том, чтобы избежать бесконечной циркуляции по сети, вызванной ошибками в таблицах маршрутизации.

Размещение маршрутизатора, соединяющего одну сеть с другой, считается оптимальным, если максимальное необходимое ВЖ для пакетов, отправляемых с этого маршрутизатора на другой компьютер в той же сети, минимально. По заданной сети Вам следует рассчитать для нее максимальное значение ВЖ, если Вы сами можете выбрать компьютер, который следует использовать в качестве маршрутизатора.

Входные данные

Первая строка содержит количество тестов c~(1 \le c \le 100). Первая строка каждого теста начинается с количества компьютеров n~(1 < n \le 10^5) в сети. Компьютеры пронумерованы числами от 0 до n - 1. Каждая из следующих n - 1 строк описывает двунаправленное соединение между компьютерами a и b~(0 \le a, b < n).

Выходные данные

Для каждого теста выведите в отдельной строке оптимальное значение ВЖ.

Пример

Входные данные #1
3
2
1 0
5
3 2
2 1
0 2
2 4
9
3 1
6 5
3 4
0 3
8 1
1 7
1 6
2 3
Выходные данные #1
1
1
2
Источник ACM ICPC German Collegiate Programming Contest 2011