#P3361. [Usaco2004 Jan]培根距离
[Usaco2004 Jan]培根距离
[USACO 2004 Jan] 培根距离
题目描述
约翰有 头奶牛,编号为 到 ,其中 号是贝茜。已知 对奶牛可以相互联系。
贝茜可以通过其他奶牛传递消息。例如,她先联系第一头奶牛,第一头再联系第二头,依此类推。一次传递经过的奶牛数量不计贝茜,但计入最后接到消息的奶牛。贝茜到另一头奶牛的培根距离,是联系该奶牛所需的最小传递长度;若能直接联系,距离为 。求最大的培根距离。
输入格式
从标准输入读入。第一行是两个整数 。接下来 行,每行给出两个奶牛编号,表示它们可以直接互相联系。
输出格式
向标准输出输出一行一个整数,表示最大的培根距离。如果存在无法通过联系到达贝茜的奶牛,输出 -1。如果只有贝茜一头奶牛,最大距离为 0。
6 7
1 2
2 3
2 4
3 4
3 5
4 5
6 5
4
样例解释
贝茜到 号奶牛的最短联系长度为 。可以经由 ,也可以经由 。
数据范围与约定
,每头奶牛的编号都在 到 之间。