#include<bits/stdc++.h>
#define MAX 1000005
using namespace std;
int t,n,m,cnt,sz;
int p[MAX],q[MAX],gr[MAX],rt[MAX];
set<int> e[MAX],fr[MAX];
int find(int x){
	for(register int i=1;i<=n;i++)
		if(!e[x].count(i)&&i!=x) return i;
}
void merge(int x,int y){
	gr[x]=gr[y]=++sz;
	fr[sz].insert(x),fr[sz].insert(y);
	rt[sz]=x;
}
void work(){
	scanf("%d%d",&n,&m);
	cnt=sz=0;
	for(register int i=1;i<=n;i++){
		e[i].clear();
		fr[i].clear();
		p[i]=q[i]=gr[i]=rt[i]=0;
	}
	for(register int i=1,a,b;i<=m;i++){
		scanf("%d%d",&a,&b);
		e[a].insert(b),e[b].insert(a);
	}
	for(register int i=1;i<=n;i++){
		if(e[i].size()==n-1){
			p[i]=q[i]=++cnt;
			continue;
		}
		if(gr[i]) continue; 
		int tp=find(i);
		if(!gr[tp]) merge(tp,i);
		else if(rt[gr[tp]]==tp){
			gr[i]=gr[tp];
			fr[gr[tp]].insert(i);
		}else if(fr[gr[tp]].size()>2){
			fr[gr[tp]].erase(tp);
			merge(tp,i);
		}else{
			rt[gr[tp]]=tp,fr[gr[tp]].insert(i);
			gr[i]=gr[tp];
		}
	}
	for(register int i=1;i<=sz;i++){
		p[rt[i]]=++cnt;
		for(int y : fr[i])
			if(y!=rt[i]) q[y]=cnt,p[y]=++cnt;
		q[rt[i]]=cnt;
	}
	for(register int i=1;i<=n;i++) printf("%d ",p[i]);printf("\n");
	for(register int i=1;i<=n;i++) printf("%d ",q[i]);printf("\n");
}
int main(){
	scanf("%d",&t);
	while(t--) work();
}//ccpy
   	      									   	  	   	