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<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
struct edge
{
	int v,nxt;
}e[2000005];
int tt,n,m,deg[500005],vis[500005],h[500005],t,d[500005];
int ans1[500005],ans2[500005],at,a[500005],bt,b[500005];
vector<int> val[500005];
void add(int u,int v)
{
//	printf("add:u=%d,v=%d\n",u,v);
	e[++t].v=v;
	e[t].nxt=h[u];
	h[u]=t;
}
void dfs(int u,int fa,int dep)
{
	vis[u]=1;
	d[u]=dep;
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa) continue;
		dfs(v,u,dep+1);
	}
}
bool cmp(const int x,const int y)
{
	return d[x]>d[y];
}
int main()
{
	scanf("%d",&tt);
	while(tt--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			deg[i]=vis[i]=h[i]=0,val[i].clear();
		t=at=0;
		for(int i=1;i<=m;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			val[u].push_back(v);
			val[v].push_back(u);
		}
		for(int i=1;i<=n;i++)
		{
			if((int)val[i].size()==n-1)
			{
				at++;
				ans1[i]=ans2[i]=at;
				continue;
			}
			if(deg[i]) continue;
			sort(val[i].begin(),val[i].end());
			int nw=1,sz=val[i].size();
			if(nw==i) nw++;
			for(int j=0;j<sz;j++)
			{
				int v=val[i][j];
				if(nw!=v) break;
				nw++;
				if(nw==i) nw++;
			}
			add(i,nw);
			add(nw,i);
			deg[nw]++,deg[i]++;
		}
		for(int i=1;i<=n;i++)
			if(!vis[i])
			{
				dfs(i,0,1);
			}
		for(int i=1;i<=n;i++)
			a[i]=i;
		sort(a+1,a+n+1,cmp);
	/*	for(int i=1;i<=n;i++)
			printf("%d ",deg[i]);
		printf("\n");*/
		for(int i=1;i<=n;i++)
		{
			int u=a[i];
			bt=0;
			for(int j=h[u];j;j=e[j].nxt)
			{
				int v=e[j].v;
				if(deg[v]==1)
					b[++bt]=v;
			}
			if(!bt) continue;
			deg[u]=0;
			for(int j=h[u];j;j=e[j].nxt)
			{
				int v=e[j].v;
				deg[v]--;
			}
		/*	printf("u=%d\n",u);
			for(int j=1;j<=bt;j++)
				printf("%d ",b[j]);
			printf("\n");*/
			for(int j=1;j<=bt;j++)
			{
				ans1[b[j]]=at+j;
				ans2[b[j]]=at+j+1;
			}
			ans1[u]=at+bt+1;
			ans2[u]=at+1;
			at+=(bt+1);
		}
		for(int i=1;i<=n;i++)
			printf("%d ",ans1[i]);
		printf("\n");
		for(int i=1;i<=n;i++)
			printf("%d ",ans2[i]);
		printf("\n");
	}
	return 0;
}