题目背景

翻译自 CCO 的 2024P3题。

时限：$6 \texttt{s}$

题目描述

有 $N$ 个城市，从 $1$ 号到 $N$ 号。有 $N-1$ 条道路将这些城市连成了一棵树，道路从 $1$ 号到 $N-1$ 号编号，第 $i$ 条道路连接城市 $u_i$ 和城市 $v_i$。

Alice 和 Bob 一起旅行，从城市 $R$ 出发。为了使他们的旅行更有趣，他们设计了一个游戏。Alice 和 Bob 轮流驾驶，从 Alice 开始。

在 Alice 的回合，她必须沿着恰好 $A$ 条他们从未走过的道路行驶。

在 Bob 的回合，他必须沿着至多 $B$ 条道路（可能为零）行驶。

在 Alice 无法按她的方式行驶时，Bob 沿着至多 $B$ 条他们以前从未驾驶过的道路行驶。

Alice 想要最大化游戏结束时所在的城市编号，而 Bob 想要它最小化。那么当两人的操作都最优时，游戏结束时他们所在的城市编号是多少？

输入格式

第一行四个整数，分别是 $N,R,A,B$。

往后 $N-1$ 行每行两个整数 $u_i,v_i$（$1\le u_i,v_i \le N,u_i \neq v_i$），描述一条道路。

输出格式

输出 Alice 和 Bob 旅程结束时所在的城市，假设他们使用最优方式。

9 6 2 1
1 3
1 6
2 4
2 5
2 7
3 9
4 6
4 8

2

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

3

提示

数据范围

Subtask	分数	约束
Subtask $1$	$4$	$2 \le N \le 300000$，$A \le B$
Subtask $2$	$16$	$2 \le N \le 300000$，任何城市最多有两条路连接，最多有一条路连接到城市 $R$。
Subtask $3$	$20$	$2 \le N \le 300$
Subtask $4$	$12$	$2 \le N \le 3000$
Subtask $5$	$16$	$2 \le N \le 100000$，$B\le 10$
Subtask $6$	$24$	$2 \le N \le 100000$
Subtask $7$	$8$	$2 \le N \le 300000$

Subtask $0$ 为样例。

样例解释 #1

在 Alice 的第一回合中，她有三个选择：前往城市 $2$、$3$ 或 $8$。

如果 Alice 前往城市 $2$，Bob 可以在他的回合中不走任何道路。这样一来，Alice 就无法沿两条从未走过的新道路行驶，因此游戏进入最终阶段。在最终阶段，Bob 可以选择不走任何道路，从而结束在城市 $2$。

如果 Alice 前往城市 $3$，Bob 可以选择从城市 $1$ 走一条道路。这样一来，Alice 就无法沿两条从未走过的新道路行驶，因此游戏进入最终阶段。在最终阶段，Bob 唯一的选择是不走任何道路，从而结束在城市 $1$。

如果 Alice 前往城市 $8$，Bob 可以选择从城市 $4$ 走一条道路。然后，Alice 可以前往城市 $5$ 或 $7$ 中的任意一个。在两种情况下，Bob 都可以从城市 $2$ 走一条道路。Alice 无法再沿两条从未走过的新道路行驶，因此游戏进入最终阶段。在最终阶段，Bob 可以选择不走任何道路，从而结束在城市 $2$。

在所有情况下，Bob 都可以使游戏结束在城市 $1$ 或 $2$。因此在最佳情况下，游戏结束在城市 $2$。