Description

画一个圈圈，上面安放 \(N(1 \le N \le 1,000)\)个孤立的点，编号依次为 \(1\) 到 \(N\)。一开始所有点都不能互相通讯。接下来开始连线，只能在相邻的点之间连线。N 和 1 是相邻的。连线的两个端点能够彼此通讯。
给出 \(P(1 \le P \le 10,000)\)个点对，你的任务是让这 \(P\) 个点对能够彼此通讯，并且连线的数量最少。比如，如果希望点 \(1\) 和点 \(3\) 能够实现通讯，必须连接点对\((1,2)\)和\((2,3)\)。如果 \(N=3\) 的话，直接连接\((3,1)\)也是可以的。

Format

Input

第 1 行：输入 1 个整数 \(N\) 和 \(P\)。
第 2..P+1 行：每行两个整数，表示希望彼此通讯的两个点。

Output

第 1 行：输出 1 个正整数，表示需要创建的最少连线数。

Sample 1

Input

5 2
1 3
4 5 

Output

3

Limitation

1s, 256MiB for each test case.

Source

东莞中学暑假测试题（1）