Description

树是一种连通且无环的图。

有根树是一种特殊的树，它指定了一个特殊的点作为根。在有根树中，如果存在一条边连接 $X$ 和 $Y$，且 $X$ 到根节点的最短路径长度小于 $Y$ 到根节点的最短路径长度，那么我们称 $Y$ 是 $X$ 的子节点。

满二叉树是一种有根树，其中每个节点要么恰好有 $2$ 个子节点，要么没有子节点。

你将获得一棵含有 $N$ 个节点的树 $G$（节点编号为 $1$ 到 $N$）。你可以删除任意数量的节点，每当你删除一个节点，与其相连的边也会一并删除。你的目标是：通过删除尽可能少的节点，使得剩下的节点可以构成一棵满二叉树（以剩余节点中的某个点作为根）。

Input Format

输入的第一行是测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行是一个整数 $N$，表示树中节点的数量。接下来的 $N - 1$ 行，每行包含两个用空格分隔的整数 $X_i$ 和 $Y_i$，表示树 $G$ 中存在一条无向边连接 $X_i$ 和 $Y_i$。

Output Format

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是当前测试用例的编号（从 $1$ 开始），$y$ 是为了将 $G$ 转换为一棵满二叉树所需删除的最少节点数。

3
3
2 1
1 3
7
4 5
4 2
1 2
3 1
6 4
3 7
4
1 2
2 3
3 4

Case #1: 0
Case #2: 2
Case #3: 1

Hint

样例说明

• 在第一个样例中，如果将节点 $1$ 作为根，那么 $G$ 已经是一棵满二叉树，因此不需要做任何操作。

• 在第二个样例中，可以删除节点 $3$ 和 $7$，然后以节点 $2$ 为根，就能形成一棵满二叉树。

• 在第三个样例中，可以删除节点 $1$，然后以节点 $3$ 为根，构成一棵满二叉树（也可以选择删除节点 $4$，并将 $2$ 作为根，同样成立）。

限制条件

• $1 \leq T \leq 100$
• $1 \leq X_i, Y_i \leq N$
• 每个测试用例保证输入构成一棵合法的连通树

小数据集（9 分）

• 时间限制：60 3 秒
• $2 \leq N \leq 15$

大数据集（21 分）

• 时间限制：120 10 秒
• $2 \leq N \leq 1000$

翻译由 ChatGPT-4o 完成。