D2. Запросы в дереве (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие этой задачи от D1  — ограничение на размер дерева.

Вам дано некорневое дерево с $$$n$$$ вершинами. В этом дереве есть некоторая скрытая вершина $$$x$$$, которую вы пытаетесь найти.

Для этого вы можете задать $$$k$$$ запросов $$$v_1, v_2, \ldots, v_k$$$, где $$$v_i$$$  — вершины дерева. После того, как вы закончили задавать все запросы, вам дается $$$k$$$ чисел $$$d_1, d_2, \ldots, d_k$$$, где $$$d_i$$$  — количество ребер на кратчайшем пути между $$$v_i$$$ и $$$x$$$. Обратите внимание, что вы знаете, какое расстояние соответствует какому запросу.

Найдите минимальное $$$k$$$, при котором существуют некоторые запросы $$$v_1, v_2, \ldots, v_k$$$, позволяющие всегда однозначно определить $$$x$$$ (независимо от того, какой $$$x$$$ выбран).

Обратите внимание, что выводить эти запросы не нужно.

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

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

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

Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$x$$$ и $$$y$$$ ($$$1 \le x, y \le n$$$), означающие, что между вершинами $$$x$$$ и $$$y$$$ в дереве есть ребро.

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

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

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

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

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

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

Во втором наборе входных данных достаточно задать единственный запрос о вершине $$$1$$$. Тогда, если $$$x = 1$$$, вы получите $$$0$$$, в противном случае  — $$$1$$$.