3361. [Usaco2004 Jan]培根距离
#3361. [Usaco2004 Jan]培根距离
题目描述
贝茜和其他奶牛联系是通过一连串的中间奶牛传递的，所以当第一头牛和贝茜联系，第二头牛和第一头牛联系，第三头牛和第二头牛联系，…一贝茜就能依次联系到其中的每一头奶牛． 联系长度是指传递过程中涉及的奶牛的数目（不包括贝茜）．任何一头奶牛（不包括贝茜）的培根距离是指从贝茜到该奶牛的最小联系长度．最小的培根距离是1（当贝茜能够直接与该奶牛联系时）.约输有C头牛，编号1到C，贝茜是1号．有P(1≤P≤10000)组奶牛相互联系．请找到最大的培根距离．
输入格式
第1行：C和P.
第2到P+1行：每行两头牛，它们之间有联系．
输出格式
输出最大培根距离．
样例
样例输入
6 7
1 2
2 3
2 4
3 4
3 5
4 5
6 5
样例输出
4
样例说明
从贝茜到6奶牛的距离是4．联系路径(2，4，5，6)和(2，3，5，6)都适合