突破点在于最后的结果一定不是一个环！所以我们枚举断边，则对于P个连接要求都只有唯一的方法：如果一个pair的两个端点在断点两侧，就分成[0,left],[right,N];否则就是[left, right]。这里区间以0开头是要考虑left=1、right=N的情况，至少得有个边（[0, 1]）表示N连向1的情况不是么。 处理一个区间内相连情况通常可以用线段树。不过我在这里用了下并查集，也挺有意思的：每个并查集的父节点是它连接着的最右端的节点，并且维护一个数量集。然后连接[x, y]的时候直接找x的父节点（最右点），再挨个向右缩点直到y即可。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int inf=1010;
 
struct E{int st,ed;}e[inf*10];
 
int to[inf];//to[i]记录与第i个点连接的最右边的点
int n,p;
int ans=0x7fffffff;
 
int main(){
	cin>>n>>p;
	for (int i=1;i<=p;i++){
		scanf("%d%d",&e[i].st,&e[i].ed);
		if (e[i].st>e[i].ed) 
			swap(e[i].st,e[i].ed);
	}
	
	for (int i=1;i<=n;i++){		//枚举断点的位置
		
		memset(to,0,sizeof(to));
		
		for (int j=1;j<=p;j++){	//对每一对要求相连的点进行讨论
			int u=e[j].st,	v=e[j].ed;
			if (u<i && i<v) {	//断点在这对点中间，则连线要从链两头绕过(实质就是环)
				to[1]=max(to[1],u);
				to[v]=n+1;		//这样在计算边数时相当于从n~1有连线 
			} 
			else 				//断点不在这对点中间，则连线从这对点中间经过即可
				to[u]=max(to[u],v);
		}
		
		int sum=0,		//统计的边数 
			r=0;		//目前已连接的最右边的点
		for (int j=1;j<=n;j++){	//逐个点统计 
			if (!to[j])		//这个点没有向右连边
				continue;
			
			if (j>r){		//then	j连的边之前一定没有连过
				sum+=to[j]-j;
				r=to[j]; 
			} 
			else 			//j连的边之前可能被连过一部分 
			if (to[j]>r){	//j~r段已经连过，r~to[j]段还没有连
				sum+=to[j]-r;
				r=to[j]; 
			}
		} 
		ans=min(ans,sum);
	}	
	
	cout<<ans;
	return 0;
}