请注意，这是错解

前置知识：负环与差分约束。

我们把女生设为 $1$，男生设为 $0$，然后对序列求前缀和。条件就变成了 $s_r=s_{l-1}+1$。

然后由于原序列每一位都是 $0$ 或 $1$，所以前缀和序列中 $\forall i\in [1,n], s_{i-1}\le s_i\le s_{i-1}+1$。

我们根据这些不等关系进行差分约束。我们要找出答案的上界，所以我们把所有不等式转化成 $s_a\le s_b+c$ 的形式。

对于所有的 $s_a\le s_b+c$，在图中从 $b$ 到 $a$ 连一条边权为 $c$ 的边，使用 SPFA 跑最短路，如果出现负环则无解。

答案即为 $dis_n$。

时间复杂度 $\mathcal O(nm)$，但是使用优先队列替换普通队列后跑得飞快。

然后我们再加一个卡时，当快要 TLE 的时候输出 -1 并结束程序即可。

#include<bits/stdc++.h>
#define R(x) x=read()
#define int long long
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-') {
			y=-1;
		}
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<3)+(x<<1)+(e-'0');
		e=getchar();
	}
	return x*y;
}
const int N=200005;
int n,m;
vector<pair<int,int> >G[N];
inline void add(int x,int y,int z) {
	G[x].push_back({y,z});
}
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
int cnt[N],dis[N];
bool vis[N];
int tot;
inline int SPFA() {
	memset(dis,0x3f,sizeof dis),dis[0]=0;
	vis[0]=1;
	q.push({0,0});
	while(!q.empty()) {
		int u=q.top().second;
		q.pop();
		vis[u]=0;
		for(auto pii:G[u]) {
			++tot;
			if(tot>20000000)return -1;    
			int v=pii.first,w=pii.second;
			if(dis[v]>dis[u]+w) {
				cnt[v]=cnt[u]+1;
				if(cnt[v]==n+1) return -1;
				dis[v]=dis[u]+w;
				if(!vis[v])vis[v]=1,q.push({dis[v],v});
			}
		}
	}
	return dis[n];
}
signed main() {
	R(n),R(m);
	for(int i=1; i<=n; ++i) {
		add(i,i-1,0),add(i-1,i,1);
	}
	for(int i=1,l,r; i<=m; ++i) {
		R(l),R(r);
		add(r,l-1,-1),add(l-1,r,1);
	}
	cout<<SPFA();
	return 0;
}