题目描述

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

见下发文件。

数据规模

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

对于 $20 \%$ 的测试点，$n \leq 10^3$。

对于另外 $15 \%$ 的测试点，$m = n - 1$。

对于另外 $15 \%$ 的测试点，$m = n$。

对于另外 $20 \%$ 的测试点，$m \leq n + 10$.