Problem A - Army buddies

const fi = '';
      fo = '';
      maxN = 100000;
var a, prev, next: array [1..maxN] of longint;
    n, s: longint;

procedure Init;
var i: longint;
begin
 for i:=1 to n do
  begin
   a[i]:=i;
   prev[i]:=i-1;
   next[i]:=i+1;
  end;
end;

procedure Work;
var i, l, r: longint;
begin
 for i:=1 to s do
  begin
   readln(l, r);
   if prev[l] > 0 then next[prev[l]]:=next[r];
   if next[r] < n+1 then prev[next[r]]:=prev[l];
   if prev[l] = 0 then write('*') else write(prev[l]);
   write(' ');
   if next[r] = n+1 then write('*') else write(next[r]);
   writeln;
  end;
end;

begin
 assign(input, fi); reset(input);
 assign(output, fo); rewrite(output);

 while true do
  begin
   readln(n, s);
   if eof then break;
   Init;
   Work;
   writeln('-');
  end;

 close(input); close(output);
end.