#P3361. [Usaco2004 Jan]培根距离

[Usaco2004 Jan]培根距离

[USACO 2004 Jan] 培根距离

题目描述

约翰有 CC 头奶牛,编号为 11 到 CC,其中 11 号是贝茜。已知 PP 对奶牛可以相互联系。

贝茜可以通过其他奶牛传递消息。例如,她先联系第一头奶牛,第一头再联系第二头,依此类推。一次传递经过的奶牛数量不计贝茜,但计入最后接到消息的奶牛。贝茜到另一头奶牛的培根距离,是联系该奶牛所需的最小传递长度;若能直接联系,距离为 11。求最大的培根距离。

输入格式

从标准输入读入。第一行是两个整数 C,PC,P。接下来 PP 行,每行给出两个奶牛编号,表示它们可以直接互相联系。

输出格式

向标准输出输出一行一个整数,表示最大的培根距离。如果存在无法通过联系到达贝茜的奶牛,输出 -1。如果只有贝茜一头奶牛,最大距离为 0。

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

样例解释

贝茜到 66 号奶牛的最短联系长度为 44。可以经由 2,4,5,62,4,5,6,也可以经由 2,3,5,62,3,5,6。

数据范围与约定

1≤P≤10 0001\le P\le 10\,000,每头奶牛的编号都在 11 到 CC 之间。