there source code



int main()
{

    read();

    if ( solve() == true)
    {
       normal();
       write();
    }
    else
    {
        printf("0\n");
    }

    return ( 0 );
}




#define HIGHT_NUMBER 100001

#define NUMBER 50005

//// sizeof(a) = 5*10^4 * sizeof(int) = 20*10^4 = 2*10^5 = 0.2 Mbyte
static int a[NUMBER]; //left hight

//sizeof(b) = 0.2 Mbyte
static int b[NUMBER];//right hight

//sizeof(ha) = 0.2 Mbyte
static int ha[NUMBER];// hight - a[i]

//sizeof(hb) = 0.2 Mbyte
static int hb[NUMBER];// hight - b[i]

//sizeof(used) = 0.2 Mbyte
static Bool_T used[NUMBER];// used[i] = true, if self, used[i] = false, if rotate used

//sizeof(res) = 0.2 Mbyte
static int res[NUMBER];// result indexes

//sizeof(r1) = 10^5 * 4 = 0.4 Mbyte
static int r1[HIGHT_NUMBER];//temporary array

//sizeof(r2) = 0.4 Mbyte
static int r2[HIGHT_NUMBER];//temporary array

/////total : 0.2 * 6 + 0.4*2 = 1.2 + 0.8 = 2 Mbyte;

static int number; // number of glass
static int hight;    // hight of glass

static int difference;
static int absDifference;
static int remainder;

void read()
{
    int i;

    scanf("%d %d", &hight, &number );


    for ( i = 1; i <= number; i++)
    {
        scanf("%d%d",&a[i],&b[i]);

        ha[i] = hight - a[i];
        hb[i] = hight - b[i];
    }
}


void write()
{
    int i;
    for(i = 1; i< number;i++)
    {
        printf("%d ", res[i]);
    }
    printf("%d\n",res[number]);
}


static
Bool_T checkRes()
{
    int i;
    for( i = 1; i <= number - 1; i++)
    {
        if (a[ res[ i + 1 ] ] !=  b[ res[ i ] ] )
            return false;
    }
    return true;
}

void normal()
{
    int i ;
    for ( i = 1; i <= number; i++ )
    {
        if (  used[ res[ i ] ] == false )
            res[ i ] = - res[ i ];
    }
}

static
int pushUp()
{
    int i;
    int rn = 0;
    for( i = 0; i <= hight; i++)
    {
        if ( r1[ i ] > 0)
        {
            res[++rn] = r1[i];
        }
    }
    return rn;
}

static
int pushDown()
{
    int i;
    int rn = 0 ;
    for(i = hight; i>= 0; i--)
    {
        if (r1[i] > 0)
        {
            res[++rn] = r1[i];
        }
    }

    return rn;
}

static
int push()
{
    return (difference < 0) ? pushUp(): pushDown();
}


static
Bool_T horizontal()
{
    int i;
    const int  h = a[ 1 ] ;

    if ( ! ( difference == 0 ) )
    {
        return false;
    }

    for(i = 1; i <= number; i++)
    {
        if (a[i] != b[i])
            return false;

        if ( ( a[i] != h ) &&  (  hb[i] != h ))
        {
            return false;
        }
        res[ i ] = i;
        used[i]  = ( ( a[ i ] == h ) ? true : false);
        if ( ! used[i] )
        {
            a[i] = hb[i];
            b[i] = ha[i];
        }
    }

    return true;
}



static
Bool_T Difficult()
{
    int i, t;
    int rn;

    //check to changeable
    //if ( !IsDifficult()  )
    //{
    //    return false;
    //}

    for(i = 1; i <= number;i++)
    {
        used[i] = true;
    }


    for(i = 0; i<= hight; i++)
        r1[i] = r2[i] = 0;

    for(i = 1 ; i<= number;i++)
    {
        if (r1[a[i]] == 0)
        {
            r1[a[i]] = i;
        }
        else if ( r2[ a[ i ] ] == 0 )
        {
            r2[a[i]] = i;
        }
        else
        {
            return false;
        }
    }

    for(i = 0; i<= hight;i++)
    {
        if ( r1[ i ] > 0 && r2[ i ] > 0 )
        {
            int r2i = r2[ i ];

            if( r1[ hb[ r2i ] ] > 0 )
            {
                return false;
            }

            r1[ hb[ r2i ] ] = r2i;

            used[ r2i ] = false ;

            a[r2i] = hb[r2i];
            b[r2i] = ha[r2i];
        }
    }

    rn = push();

    if (rn != number)
    {
        return false;
    }

    return checkRes();
}
static
Bool_T DifCheck()
{
    int i;
    for( i = 1; i<= number ; i++)
    {
        if ( a[i] - b[i] != difference )
        {
            return false ;
        }
    }

    return true;
}


Bool_T solve()
{
    difference = a[1] - b[1] ;
    absDifference = abs(difference);
    remainder = ( absDifference == 0) ? 0 : (a[1] % absDifference ) ;
    if ( DifCheck() )
        if (difference == 0)
            return horizontal();
        else
            return Difficult();


    else
        return false;
}