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:
#include<bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);(i)<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);(i)>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<':'<<x<<endl
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}
void wr(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>=10)wr(x/10);
    putchar('0'+x%10);
}
const int MAXN=5e5+10;
int A[MAXN],B[MAXN],n,m,bel[MAXN],sz[MAXN];
set<int>rem,G[MAXN],buc[MAXN];
inline void doit(int i){
	bel[i]=i;
	for(int y:rem)if(y!=i&&!G[i].count(y))buc[i].insert(y),bel[y]=i;
	sz[i]=buc[i].size();
	for(int y:buc[i])rem.erase(y);
	rem.erase(i);
}
inline void solve(){
	n=read();m=read();rem.clear();
	fp(i,1,n)G[i].clear(),bel[i]=sz[i]=A[i]=B[i]=0,rem.insert(i),buc[i].clear();
	fp(i,1,m){
		int l=read(),r=read();
		G[l].insert(r);G[r].insert(l);
	}
	fp(i,1,n)if(G[i].size()==n-1)bel[i]=-1,rem.erase(i);
	fp(i,1,n)if(!bel[i]){
		for(int x:rem)if(x!=i&&!G[i].count(x)){
			doit(i);goto ss;
		}
		int v;
		fp(j,1,n)if(i!=j&&bel[j]!=-1&&!G[i].count(j)){v=j;break;}
		assert(bel[v]!=v);
		if(sz[bel[v]]>=2){
			--sz[bel[v]];buc[bel[v]].erase(v);
			bel[v]=i;bel[i]=i;buc[i].insert(v);sz[i]=1;rem.erase(i);
		}
		else{
			bel[bel[v]]=0;buc[bel[v]].clear();sz[bel[v]]=0;rem.insert(bel[v]);rem.insert(v);
			doit(v);
		}
		ss:;
	}
	int cnt=0;
	fp(i,1,n){
		if(bel[i]==-1)A[i]=B[i]=++cnt;
		else if(bel[i]==i){
			++cnt;A[i]=cnt;B[i]=sz[i]+cnt;
			for(int x:buc[i]){
				B[x]=cnt;A[x]=++cnt;
			}
		}
	}
	fp(i,1,n)wr(A[i]),putchar(' ');puts("");
	fp(i,1,n)wr(B[i]),putchar(' ');puts("");
}
int main(){
	int tt=read();
	while(tt--)solve();
	return 0;
}