D1. Раскраска дерева (простая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии вам нужно только найти минимальное количество операций. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Дано корневое дерево$$$^{\text{∗}}$$$, состоящее из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$, где корень имеет индекс $$$1$$$, а каждая вершина изначально белая. Обозначим расстояние от корня до $$$i$$$-й вершины как $$$d_i$$$. Вы можете выполнять следующую операцию любое число раз:

  1. Выберите подмножество белых вершин $$$S$$$ так, чтобы никакие две вершины в $$$S$$$ не были соединены ребром и не имели одинаковое расстояние до вершины $$$1$$$. Формально, $$$S$$$ должно удовлетворять условиям, что для всех $$$x,y\in S$$$ и $$$x\neq y$$$, $$$d_x\neq d_y$$$ и между $$$x$$$ и $$$y$$$ нет рёбер.
  2. Покрасьте вершины в $$$S$$$ в чёрный цвет.
Ваша задача — найти минимальное количество операций, необходимых для покраски всего дерева в чёрный цвет.

$$$^{\text{∗}}$$$Деревом называется связный граф без циклов. Корневым деревом называется дерево, в котором одна из вершин специальная и называется корнем.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — количество вершин в дереве.

$$$i$$$-я из следующих $$$n-1$$$ строк содержит два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1\le u_i,v_i\le n$$$, $$$u_i\neq v_i$$$) — концы $$$i$$$-го ребра.

Гарантируется, что заданные рёбра образуют дерево.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot10^5$$$.

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

Для каждого набора входных данных на отдельной строке выведите минимальное количество операций.

Пример
Входные данные
10
5
3 1
1 2
5 1
4 1
5
3 2
2 4
2 5
1 2
5
3 4
4 1
5 1
1 2
5
2 5
3 1
2 1
3 4
5
1 3
1 5
4 3
2 4
13
2 1
3 2
4 2
5 4
6 3
7 1
8 5
9 6
10 4
11 7
12 8
13 10
10
5 7
8 1
1 10
2 8
8 4
9 4
6 1
5 3
7 8
10
7 6
3 7
6 9
7 1
9 8
5 1
3 10
9 2
1 4
10
10 6
2 8
4 10
7 5
1 2
7 10
10 9
9 1
7 3
10
6 8
9 7
4 10
5 9
4 2
3 8
6 5
1 5
1 10
Выходные данные
5
4
4
3
3
3
4
4
4
3
Примечание

В первом наборе входных данных, $$$d_1=1$$$ и $$$d_2=d_3=d_4=d_5=2$$$. Можно показать, что необходимо выполнить как минимум $$$5$$$ операций, потому что нет двух вершин, которые можно было бы обработать одновременно.

Во втором наборе входных данных, мы можем показать, что минимальное количество операций, необходимых для покраски всего дерева, равно $$$4$$$. Один из способов сделать это — покрасить вершины $$$1$$$ и $$$3$$$ в одной операции, а все $$$3$$$ остальные вершины в их собственных операциях.