有一棵树,小黄刚开始在A点,rb最开始在B点,rb天天去小黄宿舍偷东西吃,所以小黄决定追杀rb,于是开始了这样一个追杀游戏:
两人每轮都可以选择一个和自己当前位置相邻的节点移动一步(且必须移动),在任何时刻,若他们处于同一节点,则游戏结束。小黄希望游戏尽早抓到rb,rb希望尽可能晚被抓到,rb先跑,小黄想知道游戏结束时他走了多少步?
注:由于OJ的评测时间是累加的,本题给6000MS完全是由于后台测试数据过多,尽量使用scanf或更快的读入方式,且可以将本题看作时限为1000MS。
输入数据为一棵树。
第一行三个整数,n,x,y表示树的节点个数,rb的位置和小黄的位置。(n <= 1e5)
接下来 n - 1 行,表示一棵树的n - 1条无向边。
输出一个整数,表示小黄走的步数,如果小黄永远追不上,请输出-1。
5 4 1 1 2 2 3 3 4 3 5
2