CF2271H1 Personal Issues (Easy Version)

这是本题的简单版本。不同版本的区别在于，本版本中 $t \leq 1000$，$n \leq 3000$ 且所有测试用例中 $n$ 的总和不超过 $3000$。只有在你通过了所有版本的题目后，才能 hack 其他人。 对手 Axial 和 Nife 又争吵了一次，他们决定通过在一棵树上玩一个游戏来解决争端。 他们得到了一棵有 $n$ 个顶点的树，顶点编号从 $1$ 到 $n$。每个顶点上要么是 $0$，要么是 $1$。初始时，有两个互不相同的顶点 $x$ 和 $y$ 上的值为 $0$，其余所有顶点上的值都为 $1$。 两名玩家轮流操作，Axial 先手。每一回合，当前玩家选择一个值为 $1$ 的顶点 $v$，并将其变为 $0$。在改变 $v$ 的值之前，记 $c_v$ 为 $v$ 的邻居中值为 $0$ 的顶点数量。如果 $c_v=1$，那么当前玩家得 1 分，否则不得分。游戏结束时，所有顶点的值都变为 $0$。 设 $p$ 和 $q$ 分别为 Axial 和 Nife 的最终得分。Axial 想要最大化 $p-q$，而 Nife 想要最小化它。假设两人都采取最优策略，请你求出游戏结束时 $p-q$ 的值。

每份测试数据包含多个测试用例。第一行包含测试用例个数 $t$（$1 \le t \le 1000$）。接下来的每个测试用例描述如下。 每个测试用例的第一行包含三个整数 $n$、$x$ 和 $y$（$2 \leq n \leq 3000$，$1 \leq x, y \leq n$，$x \ne y$），表示树中顶点的个数，以及初始时值为 $0$ 的两个顶点编号。 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$，$u \ne v$），表示树上的一条边 $(u,v)$。 保证所给的图为一棵树。 保证所有测试用例的 $n$ 总和不超过 $3000$。

对于每个测试用例，输出一个整数，表示游戏结束时 $p-q$ 的值。

下图中，蓝色顶点初始时为 $0$，白色顶点初始时为 $1$。 对于第一个样例，初始如下：  Axial 将顶点 $3$ 变为 $0$。此时 $3$ 恰有一个邻居为 $0$，所以 Axial 得 1 分。因此 $p-q=1$。 对于第二个样例，初始如下：  Axial 可以选择将顶点 $2$ 或 $3$ 变为 $0$，都能得 1 分。随后，剩下的顶点有两个邻居为 $0$，Nife 得 0 分。因此 $p-q=1$。 对于第三个样例，初始如下：  唯一的操作是将顶点 $2$ 变为 $0$，此时它有两个邻居为 $0$，Axial 得 0 分。因此 $p-q=0$。 由 ChatGPT 5 翻译