#1887. 捉迷藏
捉迷藏
题目描述
位于城市长达三小时的小云雀杯结束了,困扰了小Z
很久的问题也得以解决。大家都争先恐后的要前往小Z
家里。去看看小Z
家的花目前是什么样子。当他们兴致勃勃的到达小Z
家里时,发现花都不见了,大家愣了一会,终于反映过来了。高喊:快报警,抓小偷了。
但是附近有这么多城市,谁知道小偷跑哪去了呢。但是因为小偷从花园走出去的,所以它身上有香味,我们每一次都可以知道他在哪一个城市。
总共有个城市,小偷已经跑到了第个城市。 有趣的是,所有的城市是一个树形结构。对于学过信息学的你来说,这个根本不算特别难的问题。
规则:警察追击小偷为回合制。但是小偷会先转移。小偷转移时也可原地不动,但是要算一次转移次数。小偷移动完成以后警察才可以移动。
小偷尽可能的拖延时间,警察要快点抓住小偷
请帮助警察,用最快的时间抓住小偷
输入格式
第一行输入和。
接下来总共行,每行输入个数表示城市和城市之间有道路,可以到达。
输出格式
共一行,输出警察抓到小偷的时候的最短时间。
样例
输入样例1
4 3
1 2
2 3
2 4
输出样例1
4
输入样例2
5 2
1 2
2 3
3 4
2 5
输出样例2
6
提示
样例解释:
图一:
小偷在号点不动
警察从号到号点
小偷在号点不动
警察从号到号点
总共过了次抓到的
样例解释
图二:
小偷从号到号点
警察从号到号点
小偷从号到号点
警察从号到号点
小偷在号点不动
警察从号到号点
总共过了次抓到的
的数据
的数据
的数据
的数据