膜爆了。㔻。

设 $dp_i$ 表示在第 $i$ 个人是母的的情况下，前 $i$ 个人有多少个人是母的，注意这里设的是位置而不是区间。

那么显然存在一个位置 $j$ 使得 $i$ 可以从 $j$ 转移过来。

考虑 $j$ 的合法性。

首先题目中说了对于任意一个区间要保证都仅仅存在一个母的，这可以转化为：任意一个区间都最多包含一个母的，最少包含一个母的。

我们对于任意一个包含 $i$ 的区间 $[L,R]$ ，只能存在一个位置有雌的，但是我们又钦定了这个位置是 $i$，所以 $j$ 一定不在任意一个包含 $i$ 的区间中，且小于所有满足条件的区间的 $L$ 的最小值，设这个值为 $minL$。

对于任意一个在 $i$ 前面且不包含 $i$ 的区间 $[L,R]$ 也必须有一个是雌的，所以我们只能让这个位置是 $j$ ，因此，$j$ 一定是在 $i$ 前面且不包含 $i$ 的区间 $[L,R]$ 中，且大于等于所有满足条件的区间的 $L$ 的最大值，设这个值为 $maxL$。

然后我们注意到 $minL$ 和 $maxL$ 是单增的，所以直接单调队列。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
bool Test_MLE_start;
constexpr int N=2*1e5+10;
int _=1,n,m,dp[N],minL[N],maxL[N];
deque<int> q;
inline int reads(){
	int c=getchar(),x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}inline void files(){
	freopen("std.in","r",stdin);
	freopen("std.out","w",stdout);
}inline void clr(){
//	Don't forget!

}bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads(),m=reads();
		for(int i=1;i<=n+1;i++) minL[i]=i;
		for(int i=1;i<=m;i++){
			int L,R;L=reads(),R=reads();
			minL[R]=min(minL[R],L);
			maxL[R+1]=max(maxL[R+1],L);
		}for(int i=n;i>=1;i--) minL[i]=min(minL[i],minL[i+1]);
		for(int j=1;j<=n+1;j++) maxL[j]=max(maxL[j],maxL[j-1]);
		for(int i=1;i<=n;i++) cout<<i<<":"<<minL[i]<<" "<<maxL[i]<<"\n";
		q.push_back(0);
		for(int i=1,j=1;i<=n+1;i++){
			for(;j<minL[i];j++){
				if(~dp[j]){
					while(!q.empty()&&dp[q.back()]<dp[j]) q.pop_back();
					q.push_back(j);
				}
			}while(!q.empty()&&q.front()<maxL[i]) q.pop_front();
			if(q.empty()) dp[i]=-1;
			else dp[i]=dp[q.front()]+(i!=n+1);
			cout<<i<<":"<<dp[i]<<"\n"; 
		}printf("%d\n",dp[n+1]);
	}return 0;
}