CF1695D2 Tree Queries (Hard Version)

此问题与 [CF1695D1 Tree Queries (Easy Version)](https://www.luogu.com.cn/problem/CF1695D1) 的唯一区别是树的大小的限定。 给定一棵无根树，有 $ n $ 个顶点。在这棵树上有一个顶点 $ x $ ,你希望找到它。 要找到 $ 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 \times 10^5 )$ 即树中的顶点数。 然后有 $ n - 1 $ 行,每行包含两个整数 $ x, y \ ( 1 \le x, y \le n )$，意味着树中顶点 $ x $ 和 $ y $ 之间有一条边。 数据保证所给的边一定形成一棵树。 数据保证每个测试点中 $ n $ 的总和不超过 $ 2 \times 10^5 $。

输出共 $t$ 行，每行给出一个非负整数，即为你需要的最小查询数。

在第一组数据中，只有一个顶点，因此不需要任何查询。 在第二组数据中，你可以进行关于节点 $ 1 $ 的单个查询从而得到 $ x $ 节点的信息。