一个档案馆保存了一张无向图的 m 条边，并按存入顺序将它们编号为 1 至 m。图有 n 个顶点，可能不连通；允许自环，也允许不同编号的边拥有相同端点。

档案馆准备封存一个非空连续编号区间 [l,r]，使这些边暂时不可使用，其他边仍可使用。

如果封存后，原来任意一对互相连通的顶点仍然互相连通，就称这次封存是安全的。路径可以改变，只要求连通关系保留。一个顶点与自身始终连通。

求安全区间 [l,r] 的数量。

输入格式

本题只有一组输入数据。

第一行包含 n、m。

接下来 m 行，第 i 行包含 u_i、v_i，表示编号为 i 的边的两个端点。

输出格式

输出安全区间数量。

数据范围

• 1 ≤ n,m ≤ 200000；
• 1 ≤ u_i,v_i ≤ n。

样例

4 5
1 2
2 3
1 3
3 4
3 4

6

说明：五个只包含一条边的区间都安全。唯一安全的长度为 2 的区间是 [3,4]，封存后保留的边 1、2、5 仍能连接全部顶点。没有更长的安全区间。

下载样例数据