思路：

肯定是要枚举断点的。。就看枚举完断点以后怎么处理了……

1.用类似并查集的思想… f[x]=max(f[x],y)表示x和y相连（一定要注意取max，，，血的教训） 复杂度O(np)

2.猥琐思路 每回枚举完断点以后sort一遍 用左右指针扫一遍就OK..

需要高超的卡时技巧就能过 复杂度：O(nplogp)

// by SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int n,p,ans=0x3fffffff,f[2005];

struct Node{int x,y;}node[10005];

int main(){

    scanf("%d%d",&n,&p);

    for(int i=1;i<=p;i++){

        scanf("%d%d",&node[i].x,&node[i].y);

        if(node[i].x>node[i].y)swap(node[i].x,node[i].y);

    }

    for(int i=1;i<n;i++){

        memset(f,0,sizeof(f));

        int cnt=0,Left=0,Right=0;

        for(int j=1;j<=p;j++)

            f[node[j].x]=max(node[j].y,f[node[j].x]);

        for(int j=i;j<=i+n;j++)

            if(j>Right&&f[j])

                cnt+=Right-Left,Left=j,Right=f[j];

            else

                Right=max(Right,f[j]);

        ans=min(ans,cnt+Right-Left);

        for(int j=1;j<=p;j++)

            if(node[j].x==i)

                swap(node[j].x,node[j].y),node[j].y+=n;

    }

    printf("%d\n",ans);

}

// by SiriusRen

#include <cstdio>

#include <algorithm>

using namespace std;

int n,p,tot=0,ans=0x3fffffff;

struct Node

{

    int x,y;

}node[30005];

bool cmp(Node x,Node y)

{

    return x.x<y.x;

}

int read()

{

    int x=0;char p=getchar();

    while(p>'9'||p<'0')p=getchar();

    while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();

    return x;

}

int main()

{

    n=read();p=read();

    for(register int i=1;i<=p;i++)

    {

        node[i].x=read();node[i].y=read();

        if(node[i].x>node[i].y)

        {

            register int temp=node[i].y;

            node[i].y=node[i].x;

            node[i].x=temp;

        }

    }

    for(register int i=1;i<n;i++)

    {

        sort(node+1+tot,node+1+tot+p,cmp);

        int Left=0,Right=0,cnt=0;

        for(int j=1;j<=p;j++)

        {

            if(node[j+tot].x<=Right)

            {

                Right=Right>node[j+tot].y?Right:node[j+tot].y;

            }

            else

            {

                cnt+=Right-Left;

                Left=node[j+tot].x;

                Right=node[j+tot].y;

            }

        }

        cnt+=Right-Left;

        ans=ans<cnt?ans:cnt;

        while(node[tot+1].x==i)

        {

            node[tot+1+p].x=node[tot+1].y;

            node[tot+1+p].y=node[tot+1].x+n;

            tot++;

        }

    }

    printf("%d\n",ans);

}