Единственное отличие этой задачи от 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$$$.
Для каждого набора входных данных выведите в отдельной строке одно целое неотрицательное число — минимальное количество запросов, которое вам необходимо.
3121 2102 42 15 73 108 66 11 34 79 6
0 1 2
В первом наборе входных данных есть только одна вершина, поэтому никаких запросов не требуется.
Во втором наборе входных данных достаточно задать единственный запрос о вершине $$$1$$$. Тогда, если $$$x = 1$$$, вы получите $$$0$$$, в противном случае — $$$1$$$.
