CF1975D.Paint the Tree

378QAQ 有一棵包含 $n$ 个顶点的树。初始时，所有顶点都是白色的。

树上有两个棋子，分别叫做 $P_A$ 和 $P_B$。$P_A$ 和 $P_B$ 分别初始位于顶点 $a$ 和 $b$。每一步，378QAQ 会按如下顺序进行操作：

1. 将 $P_A$ 移动到相邻的一个顶点。如果目标顶点是白色，则将其染成红色。
2. 将 $P_B$ 移动到相邻的一个顶点。如果目标顶点是红色，则将其染成蓝色。

初始时，顶点 $a$ 被染成红色。如果 $a=b$，则顶点 $a$ 被染成蓝色。注意，每一步两个棋子都必须移动。两个棋子可以同时位于同一个顶点。

378QAQ 想知道，将所有顶点都染成蓝色所需的最少步数。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1\leq t\leq 10^4$），表示测试用例的数量。

每组测试用例的第一行包含一个整数 $n$（$1\leq n\leq 2\cdot 10^5$）。

第二行包含两个整数 $a$ 和 $b$（$1\leq a,b\leq n$）。

接下来 $n-1$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1\leq x_i,y_i\leq n$），表示在顶点 $x_i$ 和 $y_i$ 之间有一条边。保证这些边构成一棵树。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

对于每组测试用例，输出将所有顶点染成蓝色所需的最少步数。

在第一个测试用例中，378QAQ 可以按如下顺序将所有顶点染成蓝色：

• 初始时，$P_A$ 位于顶点 $1$，$P_B$ 位于顶点 $2$。顶点 $1$ 被染成红色，顶点 $2$ 是白色。
• 378QAQ 将 $P_A$ 移动到顶点 $2$ 并将其染成红色。然后将 $P_B$ 移动到顶点 $1$ 并将其染成蓝色。
• 378QAQ 将 $P_A$ 移动到顶点 $1$。然后将 $P_B$ 移动到顶点 $2$ 并将其染成蓝色。

由 ChatGPT 4.1 翻译