#include <stdio.h>
typedef struct
{
int l, r;
}soldier;
int main()
{
soldier sold[101000];
int i, s, b, r, l;
while(scanf("%d %d", &s, &b) && s)
{
for(i=1;i<=s;i++)
{
sold[i].l = i-1;
sold[i].r = i+1;
}
sold[s].r = 0;
for(i=0;i<b;i++)
{
scanf("%d%d", &l, &r);
sold[sold[l].l].r = sold[r].r;
sold[sold[r].r].l = sold[l].l;
if(sold[l].l == 0 && sold[r].r == 0) printf("* *\n");
else if(sold[l].l == 0) printf("* %d\n", sold[r].r);
else if(sold[r].r == 0) printf("%d *\n", sold[l].l);
else printf("%d %d\n", sold[l].l, sold[r].r);
}
printf("-\n");
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+Cgp0eXBlZGVmIHN0cnVjdAp7CiAgICBpbnQgbCwgcjsKfXNvbGRpZXI7CgppbnQgbWFpbigpCnsKICAgIHNvbGRpZXIgc29sZFsxMDEwMDBdOwogICAgaW50IGksIHMsIGIsIHIsIGw7CiAgICB3aGlsZShzY2FuZigiJWQgJWQiLCAmcywgJmIpICYmIHMpCiAgICB7CiAgICAgICAgZm9yKGk9MTtpPD1zO2krKykKICAgICAgICB7CiAgICAgICAgICAgIHNvbGRbaV0ubCA9IGktMTsKICAgICAgICAgICAgc29sZFtpXS5yID0gaSsxOwogICAgICAgIH0KICAgICAgICBzb2xkW3NdLnIgPSAwOwogICAgICAgIGZvcihpPTA7aTxiO2krKykKICAgICAgICB7CiAgICAgICAgICAgIHNjYW5mKCIlZCVkIiwgJmwsICZyKTsKICAgICAgICAgICAgc29sZFtzb2xkW2xdLmxdLnIgPSBzb2xkW3JdLnI7CiAgICAgICAgICAgIHNvbGRbc29sZFtyXS5yXS5sID0gc29sZFtsXS5sOwogICAgICAgICAgICBpZihzb2xkW2xdLmwgPT0gMCAmJiBzb2xkW3JdLnIgPT0gMCkgcHJpbnRmKCIqICpcbiIpOwogICAgICAgICAgICBlbHNlIGlmKHNvbGRbbF0ubCA9PSAwKSBwcmludGYoIiogJWRcbiIsIHNvbGRbcl0ucik7CiAgICAgICAgICAgIGVsc2UgaWYoc29sZFtyXS5yID09IDApIHByaW50ZigiJWQgKlxuIiwgc29sZFtsXS5sKTsKICAgICAgICAgICAgZWxzZSBwcmludGYoIiVkICVkXG4iLCBzb2xkW2xdLmwsIHNvbGRbcl0ucik7CiAgICAgICAgfQogICAgICAgIHByaW50ZigiLVxuIik7CiAgICB9CiAgICByZXR1cm4gMDsKfQo=