Description
Farmer John想给他的N(2≤N≤1000000000)头奶牛拍照，奶牛们排成一排，编号为1到N。每张照片都能拍摄到队列中连续的部分奶牛，而且FJ希望最终每头奶牛都至少在一张照片中出现过。
遗憾的是，有K(1≤K≤1000)对不友好的奶牛，其中的每对奶牛拒绝出现在同一张照片中。
给出这K对不友好的奶牛，请帮助FJ计算一下，他至少要拍摄多少张照片。
Input
第一行，两个整数N和K
接下来K行，每行两个整数A_i和B_i，表示位置分别为A_i和B_i的两头奶牛不友好，拒绝出现在同一张照片中。
Output
一行，一个整数，表示为了达成拍摄目标，FJ需要最少拍摄多少张照片
HINT
样例说明：
FJ需要拍摄3张照片:
照片1，从1到2
照片2，从3到5
照片3，从6到7