P17547 [JAG 2026 Summer Camp #2] Tree + 1

给定一棵有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。 你的目标是按照以下步骤，让这棵树的每个顶点都被访问至少一次。 1. 任意选择两个顶点，在它们之间添加一条边。 2. 任意选择一个顶点，并访问它。 3. 将以下操作重复任意多次：从与当前访问的顶点有边相连的顶点中任意选择一个，并访问该顶点。每次操作的代价为 $1$。 求达成目标所需的最小总代价。

输入包含一组或多组测试数据。第一行包含一个整数 $t$（$1\le t\le 10^5$），表示测试数据组数。每组测试数据的格式如下： ```text N u_1 v_1 u_2 v_2 ... u_{N-1} v_{N-1} ``` 整数 $N$（$2\le N\le 5\times 10^5$）表示给定树的顶点数。 对于每个整数 $i$（$1\le i\le N-1$），整数 $u_i,v_i$ 表示第 $i$ 条边的两个端点的编号。 给定的图构成一棵树。 所有测试数据的 $N$ 之和不超过 $5\times 10^5$。

对于每组测试数据，输出达成目标所需的最小总代价。

对于第一组测试数据，在顶点 $4$ 和 $6$ 之间添加一条边后，可以从顶点 $1$ 出发，按 $1\to 2\to 3\to 4\to 6\to 5$ 的顺序访问顶点，总代价为 $5$。