题目描述

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% 的数据，$2\le N\le 20$，$0\le M\le 20$；

100% 的数据，$2\le N\le 40000$，$0\le M\le 10^6$，$1\le U_i,V_i\le N$。