#include <cstdio>
#include <cstring>

using namespace std;

const int MAXN = 100005;

int N, M, L[MAXN], R[MAXN];
bool p[MAXN];

int findl(int v){
	if(v == 0) return 0;
	if(p[v]) return v;
	L[v] = findl(L[v]);
	return L[v];
}

int findr(int v){
	if(v == N + 1) return 0;
	if(p[v]) return v;
	R[v] = findr(R[v]);
	return R[v];
}

int main(){
	while(scanf("%d%d", &N, &M) && N && M){
		for(int i = 1; i <= N; ++i)
			L[i] = i - 1;
		for(int i = 1; i <= N; ++i)
			R[i] = i + 1;
		memset(p, true, sizeof(p));
		for(int i = 0; i < M; ++i){
			int x, y;
			scanf("%d%d", &x, &y);
			p[x] = false; p[y] = false;
			int l = findl(x); int r = findr(y);
			L[r] = l; R[l] = r;
			if(l == 0) printf("* ");
			else printf("%d ", l);
			if(r == 0) printf("*\n");
			else printf("%d\n", r);
		}
		puts("-");
	}
}
