#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)

int const N = 500000;
int lst[N + 1], n, m, p[N + 1], q[N + 1], fr[N + 1], pa[N + 1], zp[N + 1];
vector<int> gr[N + 1], g[N + 1];
queue<int> qu;

int P(int v) { return zp[v] ? zp[v] = P(zp[v]) : v; }

void solve(){
	scanf("%d%d", &n, &m);
	f(i, 1, n + 1){
		gr[i].clear();
		g[i].clear();
		fr[i] = 0;
		pa[i] = 0;
		zp[i] = 0;
	}
	
	f(i, 0, m){
		int a, b;
		scanf("%d%d", &a, &b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	int z = n;
	f(i, 1, n + 1)if ((int)g[i].size() + 1 == n){
		p[i] = q[i] = z--;
		fr[i] = -1;
	}else {
		sort(g[i].begin(), g[i].end());
		f(j, 0, g[i].size()){
			int t = j + 1;
			if (t >= i)++t;
			if (g[i][j] != t){
				pa[i] = t;
				break;
			}
		}
		if (pa[i] == 0){
			pa[i] = g[i].size() + 1;
			if (pa[i] >= i)++pa[i];
		}
		
		int z = P(pa[i]);
		if (P(i) == z){
			pa[i] = 0;
			continue;
		}else {
			zp[i] = z;
		}
		
		++fr[pa[i]];
	}
	
	f(i, 1, n + 1)if (fr[i] == 0)qu.push(i);
	while (!qu.empty()){
		int v = qu.front();
		qu.pop();
		if (gr[v].empty()){
			if (pa[v])gr[pa[v]].push_back(v);
			else gr[lst[v]].push_back(v);
		}else {
			gr[v].push_back(v);
			reverse(gr[v].begin(), gr[v].end());
			lst[pa[v]] = v;
		}
		
		if (pa[v] && --fr[pa[v]] == 0)qu.push(pa[v]);
	}
	
	f(v, 1, n + 1)if (!gr[v].empty()){
		f(j, 0, gr[v].size())p[gr[v][j]] = z - j;
		f(j, 1, gr[v].size())q[gr[v][j]] = z - j + 1;
		z -= gr[v].size();
		q[v] = z + 1;
	}
	
	f(i, 1, n + 1)printf("%d%c", p[i], i == n ? '\n' : ' ');
	f(i, 1, n + 1)printf("%d%c", q[i], i == n ? '\n' : ' ');
}

int main(){
	int t;
	scanf("%d", &t);
	while (t--)solve();
}
