「CCO 2024」Summer Driving

题目描述

Alice 和 Bob 在加拿大的安大略省一起旅行。为了让路途更加有趣，他们设计了一个游戏。

安大略省有 $N$ 个城市，编号从 $1$ 到 $N$。连接这些城市的道路有 $N-1$ 条，编号从 $1$ 到 $N-1$。利用这些道路，可以从任何一个城市到达其他任何城市。

他们从城市 $R$ 开始旅行。游戏规则如下：

• Alice 和 Bob 轮流开车，Alice 先开。
• Alice 每次开车时，必须沿着正好 $A$ 条他们之前从未走过的（无论哪个方向）道路行驶。
• Bob 每次开车时，可以选择沿着最多 $B$ 条不同的道路行驶（也可能不走任何路），但这些道路中可能包括之前走过的路。
• 随着旅行的进行，最终会出现一种情况：Alice 无法再找到正好 $A$ 条他们从未走过的道路行驶了。这时，游戏将进入最终阶段，Alice 不再开车。
• 在最终阶段，Bob 可以选择沿着最多 $B$ 条他们之前从未走过的道路行驶。

Alice 想去编号尽可能大的城市，而 Bob 想去编号尽可能小的城市。如果他们都发挥最优策略，旅行最终会在哪个城市结束呢？

输入格式

第一行包含四个空格隔开的整数 $N, R, A, B$ $(1 \leq R, A, B \leq N)$。

接下来 $N-1$ 行，每行包含两个空格隔开的整数 $u_i, v_i$ $(1 \leq u_i, v_i \leq N, u_i \neq v_i)$，描述一条道路，连接城市 $u_i$ 和 $v_i$。

输出格式

输出根据最优策略旅行结束后，Alice 和 Bob 到达的城市编号。

样例 1

输入

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

输出

2

解释

在 Alice 第一次开车时，她有三个选择：去 $2$ 号城市，$3$ 号城市，$8$ 号城市。

• 如果 Alice 去 $2$ 号城市，Bob 可以选择不走任何路。那么，Alice 就无法再找到正好 $2$ 条他们从未走过的道路行驶了，游戏进入最终阶段。Bob 也可以选择不走任何路，最终到达 $2$ 号城市。
• 如果 Alice 去 $3$ 号城市，Bob 可以选择开一条路去 $1$ 号城市。那么，Alice 就无法再找到正好 $2$ 条他们从未走过的道路行驶了，游戏进入最终阶段。Bob 此时只能选择不走任何路，最终到达 $1$ 号城市。
• 如果 Alice 去 $8$ 号城市，Bob 可以选择开一条路去 $4$ 号城市。接着，Alice 可以去 $5$ 号城市或 $7$ 号城市。在这两种情况下，Bob 都可以选择开一条路去 $2$ 号城市。Alice 就无法再找到正好 $2$ 条他们从未走过的道路行驶了，游戏进入最终阶段。Bob 可以选择不走任何路，最终到达 $2$ 号城市。

在所有情况下，Bob 都可以迫使游戏在 $1$ 号或 $2$ 号城市结束。由于 Bob 无法迫使游戏在 $1$ 号城市结束，因此在最优策略下，游戏将在 $2$ 号城市结束。

样例 2

输入

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

输出

3

数据范围与提示