追逐游戏

TimeLimit:6000MS  MemoryLimit:128MB
64-bit integer IO format:%lld
未提交 | 登录后收藏
Problem Description

有一棵树,小黄刚开始在A点,rb最开始在B点,rb天天去小黄宿舍偷东西吃,所以小黄决定追杀rb,于是开始了这样一个追杀游戏:

两人每轮都可以选择一个和自己当前位置相邻的节点移动一步(且必须移动),在任何时刻,若他们处于同一节点,则游戏结束。小黄希望游戏尽早抓到rb,rb希望尽可能晚被抓到,rb先跑,小黄想知道游戏结束时他走了多少步?

注:由于OJ的评测时间是累加的,本题给6000MS完全是由于后台测试数据过多,尽量使用scanf或更快的读入方式,且可以将本题看作时限为1000MS。

Input

输入数据为一棵树。

第一行三个整数,n,x,y表示树的节点个数,rb的位置和小黄的位置。(n <= 1e5)

接下来 n - 1 行,表示一棵树的n - 1条无向边。

Output

输出一个整数,表示小黄走的步数,如果小黄永远追不上,请输出-1。

SampleInput
5 4 1
1 2
2 3
3 4
3 5
SampleOutput
2
Submit
题目统计信息详细
总AC数7
通过人数5
尝试人数6
总提交量32
AC率15.63%
AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题,请不要查看标签
如果您已经通过了该题,请务为该题贴上标签
作者
Satan666

T^T Online Judge

[BUG反馈] [FAQ] [闽ICP备17026590号-1]
当前版本:3.24 系统时间: