UVa 12356 - Army Buddies

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("lld%lld",&a,&b)
#define sf3(a,b,c) scanf("lld%lld%lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("lld%lld",a,b)
#define pf3(a,b,c) printf("lld%lld%lld",a,b,c)
#define nl printf("\n")
#define ll long long
#define pb push_back
#define MPI map<int,int>mp
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
main()
{
    long  n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0)
            break;
        long i,l,r,right[100005]= {0},left[100005]= {0};
        for(i=1; i<=n; i++)
        {
            left[i]=i-1;
            right[i]=i+1;
        }
        left[1]=-1;
        right[n]=-1;
        for(i=1; i<=m; i++)
        {
            cin>>l>>r;
            left[right[r]]=left[l];
            if(left[l]!=-1)
                cout<<left[l]<<" ";
            else
                cout<<"* ";
            right[left[l]]=right[r];
            if(right[r]!=-1)
                cout<<right[r]<<endl;
            else
            {
                cout<<"*"<<endl;
            }

        }
        cout<<"-"<<endl;
    }
}