题目描述

Alice 所在的银河里，一共有n个星球，星球之间通过m条边相连。

有一股邪恶势力在 1 号星球建立了基地，在每一个银河年，邪恶势力都会进行扩张。具体来说，在第 i 个银河年，所有和 1 号星球距离等于 i 的星球都会被邪恶势力占领。

现在 Alice 想在同一时间选择一个点建立一个正义势力，正义势力的扩张和邪恶势力的扩张遵循同一个形式。正义势力和邪恶势力均不能扩张到一个已经被另一方占领的星球。如果两股势力同时扩张到一个星球，那么这个星球就继续保持中立。

现在Alice想知道，通过合理建立基地，邪恶势力最少占领多少个星球？Alice的基地不能建在一号星球。

输入格式

第一行两个正整数 n, m。

接下来 m 行，每行两个整数 x, y 表示一条边。

数据保证 n 个点两两联通，且没有重边和自环。

星球从 1 到 n 标号。

星球 A 和星球 B 的距离指的是 A 到 B 经过边最少的路径的边数。

初始是第 0 个银河年。

输出格式

一行一个整数表示答案。

样例输入1

3 2
1 2
1 3

样例输出1

2

样例输入输出2

见下发文件。

数据规模

测试点编号	\(n\)	\(m\)
1~4	\( n \leq 10^3\)	\( m \leq n+100\)
5~7	\(n \leq 10^5\)	\(m = n-1\)
8~10	\(n \leq 10^5\)	\(m=n\)
11~14	\(n \leq 10^5\)	\( m \leq n+10\)
15~20	\(n \leq 10^5\)	\( m \leq n+100\)

对于所有数据，\(2 \leq n \leq 10^5,n-1 \leq m \leq n+100,1 \leq x,y \leq n\)。

下发文件

ssfz联测 下发文件