吃饭路上也要锻炼
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
Farmer John 有 N 个农场，编号为 1 ~ N。
有 M 条无向道路，每条路连接两个不同的农场。
任意两个农场间最多只有一条直接道路。
牛圈在 1 号农场，牛餐厅在 2 号农场。
每天，奶牛们从牛圈去餐厅吃饭。
奶牛们希望走尽可能短的路。可是不论它们如何走，它们发现，从牛圈到餐厅至少要经过 5 条道路。
原来现有的 M 条道路是 John 设计好的，他希望奶牛们时刻要注意锻炼。
每天，John 要穿梭于各个农场。
所以他想要再修建一些道路，以方便他的出行。
但是，他不希望奶牛们从牛圈去餐厅就餐时可以找到少于 5 条道路的路径。
问：在满足以上条件下，John 最多可以再修建多少条道路？
注：任意两个农场间最多只允许存在一条直接道路。不能修建连接同一个农场的道路。
输入格式
第一行：两个整数 N M；
接下来 M 行：每行两个整数 Ui, Vi ，表示 Ui, Vi 之间已经存在一条道路。
输出格式
一个整数，表示 John 最多可以再修建的道路条数。
样例输入
7 6
1 3
3 4
4 5
5 6
6 7
6 2
样例输出
2
数据范围
30~40% 的数据，，；
100% 的数据，，，。
