Migrated from Lutece 3195 Polygon Cutting

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给你一个 $n$ 个顶点的凸多边形，顶点编号顺时针为 $1\sim n$。现在进行 $m$ 次裁剪操作，每次选择两个顶点，编号为 $u_i,v_i$，沿这两个顶点的连线进行裁剪（不存在 $3$ 条不同的裁剪线相交于多边形内同一点）。求 $m$ 次裁剪后多边形被裁剪成多少份。

Input

第一行两个正整数 $n,m$，表示多边形的顶点数和裁剪次数。
接下来 $m$ 行，每行两个正整数 $u_i,v_i$，表示第 $i$ 次裁剪选择的两个顶点。
可能有重复的裁剪线，保证删除重复后无三线共点。

Output

输出一个整数，即多边形裁剪后的份数。

Samples

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

8

Constraints

$4\leq n\leq 2×10^5$ $1\leq m\leq 2×10^5$ $1\leq u_i,v_i\leq n,1<|u_i-v_i|<n-1$

Note

样例中裁剪后的多边形如下：

一共被分成了8个部分。