题目背景

翻译自 CCO 的 2024P3题。

时限：$6 \texttt{s}$

题目描述

有 $N$ 个城市，从 $1$ 号到 $N$ 号。有 $N-1$ 条道路，从 $1$ 号到 $N-1$ 号，其中第 $i$ 条道路连接城市 $u_i$ 和城市 $v_i$。

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

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

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

在 Alice 无法按她的方式行驶时，鲍勃沿着至多 $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$），描述一条道路。

输出格式

输出爱丽丝和鲍勃旅程结束时所在的城市，假设他们使用最优方式。

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 $0$ 为样例。

样例解释 #1

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

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

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

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

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