UVa 12356 - Army Buddies

//\\__ hr1212 __//\\

import java.io.*;
import java.math.*;
import java.util.*;

public class Uva12356{

static int i,n,m,z,x,y,j,k,l,r,s,b;
static int a[],L[],R[];
static String p,q;
static int MAX=1000010;

public static void main(String[] args) throws IOException{
InputReader in=new InputReader(System.in);
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
PrintWriter out=new PrintWriter(System.out);

while(true){
b=in.nextInt();s=in.nextInt();
if(b==0 && s==0)
break;
L=new int[MAX];
R=new int[MAX];
for(i=1;i<=b;i++){
L[i]=i-1;
R[i]=i+1;
}
R[b]=0;
for(i=0;i<s;i++){
l=in.nextInt();r=in.nextInt();
if(L[l]!=0)
out.print(L[l]+" ");
else
out.print("* ");

if(R[r]!=0)
out.println(R[r]);
else
out.println("*");

R[L[l]]=R[r];
L[R[r]]=L[l];
}
out.println("-");
}
out.close();

}
static class InputReader {

private InputStream stream;
private byte[] buf = new byte[8192];
private int curChar;
private int snumChars;
private SpaceCharFilter filter;

public InputReader(InputStream stream) {
this.stream = stream;
}

public int snext() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}

public int nextInt() {
int c = snext();
while (isSpaceChar(c))
c = snext();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = snext();
}

int res = 0;

do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = snext();
} while (!isSpaceChar(c));

return res * sgn;
}

public long nextLong() {
int c = snext();
while (isSpaceChar(c))
c = snext();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = snext();
}

long res = 0;

do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = snext();
} while (!isSpaceChar(c));

return res * sgn;
}

public String readString() {
int c = snext();
while (isSpaceChar(c))
c = snext();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = snext();
} while (!isSpaceChar(c));
return res.toString();
}

public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}

public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
}