Problem: Nezzar designs a brand new game "Hidden Permutations" and shares it with his best friend, Nanako.

At the beginning of the game, Nanako and Nezzar both know integers n and m. The game goes in the following way:

  * Firstly, Nezzar hides two permutations p_1,p_2,…,p_n and q_1,q_2,…,q_n of integers from 1 to n, and Nanako secretly selects m unordered pairs (l_1,r_1),(l_2,r_2),…,(l_m,r_m); 
  * After that, Nanako sends his chosen pairs to Nezzar; 
  * On receiving those m unordered pairs, Nezzar checks if there exists 1 ≤ i ≤ m, such that (p_{l_i}-p_{r_i}) and (q_{l_i}-q_{r_i}) have different signs. If so, Nezzar instantly loses the game and gets a score of -1. Otherwise, the score Nezzar gets is equal to the number of indices 1 ≤ i ≤ n such that p_i ≠ q_i. 



However, Nezzar accidentally knows Nanako's unordered pairs and decides to take advantage of them. Please help Nezzar find out two permutations p and q such that the score is maximized.

Input

The first line contains a single integer t (1 ≤ t ≤ 5 ⋅ 10^5) — the number of test cases.

The first line of each test case contains two integers n,m (1 ≤ n ≤ 5 ⋅ 10^5, 0 ≤ m ≤ min((n(n-1))/(2),5 ⋅ 10^5)). 

Then m lines follow, i-th of them contains two integers l_i,r_i (1 ≤ l_i,r_i ≤ n, l_i ≠ r_i), describing the i-th unordered pair Nanako chooses. It is guaranteed that all m unordered pairs are distinct.

It is guaranteed that the sum of n for all test cases does not exceed 5 ⋅ 10^5, and the sum of m for all test cases does not exceed 5⋅ 10^5.

Output

For each test case, print two permutations p_1,p_2,…,p_n and q_1,q_2,…,q_n such that the score Nezzar gets is maximized.

Example

Input


3
4 2
1 2
3 4
6 4
1 2
1 3
3 5
3 6
2 1
1 2


Output


1 2 3 4
3 4 1 2
2 3 4 1 6 5
1 4 3 2 5 6
1 2
1 2

Note

For first test case, for each pair given by Nanako:

  * for the first pair (1,2): p_1 - p_2 = 1 - 2 = -1, q_1 - q_2 = 3 - 4 = -1, they have the same sign; 
  * for the second pair (3,4): p_3 - p_4 = 3 - 4 = -1, q_3 - q_4 = 1 - 2 = -1, they have the same sign. 



As Nezzar does not lose instantly, Nezzar gains the score of 4 as p_i ≠ q_i for all 1 ≤ i ≤ 4. Obviously, it is the maximum possible score Nezzar can get.

Solution (in CPP):

Solution:
/*
{
######################
#       Author       #
#        Gary        #
#        2021        #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
//    int x=0;
//    char ch=getchar();
//    while(ch<'0'||ch>'9'){
//        ch=getchar();
//    }
//    while(ch>='0'&&ch<='9'){
//        x=(x<<1)+(x<<3)+(ch^48);
//        ch=getchar();
//    }
//    return x;
//}
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
const int MAXN=5e5+233;
int n,m;
set<int> g[MAXN];
vector<int> tree[MAXN];
vector<int> dsu[MAXN];
int fa[MAXN];
int root(int now){
	return fa[now]=(fa[now]==now? now:root(fa[now]));
}
set<int> roots;
void merge(int u,int v){
	roots.erase(u);
	fa[u]=v;
	for(auto it:dsu[u]){
		dsu[v].PB(it);
	}
	dsu[u].clear();
}
int z[MAXN],t[MAXN];
int cnt=0;
bool go(int now,int pre){
	if(pre==-1&&tree[now].empty()){
		z[now]=t[now]=++cnt;
		return 0;
	}
	vector<int> sing;
	int last=-1;
	for(auto it:tree[now]) if(it!=pre){
		last=it;
//		cout<<now<<"->"<<it<<endl;
		if(!go(it,now)){
			sing.PB(it);
		}
	}
	if(sing.empty()){
		if(pre==-1){
			t[now]=z[now]=++cnt;
			swap(t[now],t[last]);
		}
		return 0;
	}
	else{
		t[now]=z[now]=++cnt;
		for(auto it:sing){
			t[it]=z[it]=++cnt;
			swap(t[it],t[now]);
		}
		return 1;
	}
}
void solve(){
	cnt=0;
	roots.clear();
	scanf("%d%d",&n,&m);
	rb(i,1,n) fa[i]=i,dsu[i].clear(),dsu[i].PB(i),tree[i].clear(),g[i].clear(),roots.insert(i); 
	rb(i,1,m){
		int u,v;
		scanf("%d%d",&u,&v);
		g[u].insert(v);
		g[v].insert(u); 
	}
	rb(i,1,n){
		int rt=root(i);
		vector<int> tmp;
		for(auto ite=roots.begin();ite!=roots.end();++ite){
			if(rt!=*ite){
				for(auto it:dsu[*ite]){
					if(g[i].find(it)!=g[i].end());
					else{
						tree[i].PB(it);
						tree[it].PB(i);
						tmp.PB(*ite);
						break;				
					}
				}
			}
		}
		for(auto it:tmp){
			if(dsu[it].size()>dsu[rt].size()){
				swap(it,rt);
			}
			merge(it,rt); 
		}
	}
	rb(i,1,n) if(root(i)==i){
		go(i,-1);	
	}
	rb(i,1,n){
		printf("%d ",z[i]);
	}
	puts("");
	rb(i,1,n){
		printf("%d ",t[i]);
	}
	puts("");
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--) solve();	
	return 0;
}