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>
#define it register int
#define ct const int
#define il inline
using namespace std;
typedef long long ll;
#define rll register ll
#define cll const ll
#define mkp make_pair
#define fir first
#define sec second
#define P 998244353
namespace io{
	il char nc(){
		static char buf[100000],*p1=buf,*p2=buf;
		return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; 
	}
	template <class I> 
	il void fr(I &num){
		num=0;register char c=nc();it p=1;
		while(c<'0'||c>'9') c=='-'?p=-1,c=nc():c=nc();
		while(c>='0'&&c<='9') num=num*10+c-'0',c=nc();
		num*=p;
	}
	char obuf[1000001],*os=obuf, *ot = obuf + 1000001;
	il void flush(){fwrite(obuf,1,os-obuf,stdout),os=obuf;}
	il void putc(const char x){*os++=x,os==ot?flush():void();}
	template<class I>
	il void wr(I x){
		x<0?putc('-'),x=-x:0;
		static char qu[65];
		char *tmp=qu;
		do *tmp++=(x%10)^'0';while(x/=10);
		while(tmp--!=qu) putc(*tmp);
	}
	struct flusher{ ~flusher() { flush(); } }_;
}
using namespace io;
const int N=1000005;
int T,n,m,f[N],rd[N],o1[N],o2[N];
bool vs[N];
set<int> g[N];
vector<int> o[N],a[N];
il int fd(ct x){return f[x]^x?f[x]=fd(f[x]):x;}
il void dfs(ct x,ct fa){
	vs[x]=1;
	for(const auto &j : o[x])
		if(j^fa) dfs(j,x),a[j].empty()?a[x].push_back(j),0:0;
}
int main(){ 
	fr(T);it i,j,u,v;
	while(T--){
		fr(n),fr(m);
		for(i=1;i<=n;++i) rd[i]=vs[i]=0,f[i]=i,g[i].clear(),o[i].clear(),a[i].clear();
		for(i=1;i<=m;++i) fr(u),fr(v),g[u].insert(v),g[v].insert(u),++rd[u],++rd[v];
		for(i=1;i<=n;++i)
			if(rd[i]<n-1){
				g[i].insert(i),j=1;
				for(const auto &p : g[i]){if(j^p) break;++j;}
				g[i].erase(i),u=fd(i),v=fd(j),u^v?o[i].push_back(j),o[j].push_back(i),f[u]=v:0;
			}
		for(i=1;i<=n;++i)
			if(!vs[i]&&!o[i].empty())
				dfs(i,0),a[i].empty()?a[o[i][0]].push_back(i),0:0;
		for(i=1,u=0;i<=n;++i){
			if(o[i].empty()){++u,o1[i]=o2[i]=u;continue;}
			if(a[i].size()){
				j=0;for(const int &p : a[i]) ++j,o1[p]=j+u,o2[p]=j+1+u;
				o1[i]=a[i].size()+u+1,o2[i]=u+1,u+=a[i].size()+1;
			}
		}
		for(i=1;i<=n;++i) printf("%d ",o1[i]);puts("");
		for(i=1;i<=n;++i) printf("%d ",o2[i]);puts("");
	}
	return 0;
}