cerc2

#include <fstream>

using namespace std;
const int nmax=501;
const int mmax=nmax*(nmax-3)/2;
struct segm
{
    int p1,p2,lung;
};
int n,j;
long int m,i,p[nmax],l[nmax],ind[mmax],inters;
segm per[mmax],s;

void calc(segm &s)
{
    if(s.p2-s.p1<=n+s.p1-s.p2)
        s.lung=s.p2-s.p1-1;
    else
        s.lung=n+s.p1-s.p2-1,swap(s.p1,s.p2);
}

void citire()
{
    ifstream f("cerc2.in");
    f>>n>>m;
    long int i=0;
    while(f>>s.p1>>s.p2)
    {
        calc(s);
        if(s.lung==0)
            continue;
        ++p[s.p1];
        ++p[s.p2];
        ++l[s.lung];
        ++i;
        per[i]=s;
    }
    m=i;
    f.close();
}

void sortare()
{
    long int i,j;
    for(i=2;i<=n;++i)
        l[i]+=l[i-1];
    for(j=1;j<=m;++j)
        i=per[j].lung,ind[l[i]]=j,--l[i];
}

int main()
{
     citire();
     sortare();
     inters=0;
     for(i=1;i<=m;++i)
    {
        s=per[ind[i]];
        j=s.p1%n+1;
        while(j!=s.p2)
        {
            inters=(inters+p[j])%1000000;
            j=j%n+1;
        }
        --p[s.p1],--p[s.p2];
    }
    ofstream g("cerc2.out");
    g<<inters<<'\n';
    g.close();
    return 0;
}