给定一个包含 $n$ 个顶点和 $m$ 条边的简单无向图，保证 $m < \frac{n(n-1)}{2}$。

我们定义一个无向图是传递的，当且仅当对于任意两个不同的顶点 $u, v$：如果图中存在一条从 $u$ 到 $v$ 的路径，那么图中必须存在一条连接 $u$ 和 $v$ 的边。

现在你需要向图中添加一些无向边（至少添加一条边）。你需要确保添加边之后，该图仍然是一个简单无向图且是传递的。

问题是，至少需要添加多少条边？

回想一下，简单无向图是指任意两个顶点之间不超过一条边，且没有边连接同一个顶点的无向图。

输入格式

第一行包含两个整数 $n, m$ ($3 \le n \le 10^6, 1 \le m \le \min(10^6, \frac{n(n-1)}{2} - 1)$)，表示给定图的顶点数和边数。

接下来 $m$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n, u \neq v$)，表示给定图中的一条边。保证该图是简单的。

输出格式

一个正整数，表示你需要添加的最少边数。

样例

输入 1

4 3
1 2
1 3
2 3

输出 1

3