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<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<cassert>
#define ll long long
using namespace std;
int n,m;
int ql[500009],qr[500009];
int ansp[500009],ansq[500009];
int deg0[500009],del[500009];
int f[500009];
int st[500009],tot;
int vis[500009];
vector<int> g0[500009],g1[500009];
set<int> g2[500009];
void clr()
{
	memset(deg0,0,(n+1)*4);
	memset(del,0,(n+1)*4);
	memset(vis,0,(n+1)*4);
	for(int i=1;i<=n;i++)
		g0[i].clear(),g1[i].clear(),g2[i].clear();
}
int fnd(int x)
{
	return x==f[x]?x:f[x]=fnd(f[x]);
}
void bfs(int s)
{
	queue<int> q;
	f[s]=fnd(s+1);
	q.push(s);
	while(!q.empty())
	{
		int x=q.front();
		st[++tot]=x;
		q.pop();
		int ls=0;
		g0[x].push_back(n+1);
		for(int rb:g0[x])
		{
			// printf("x:%d rb:%d\n",x,rb);
			if(rb-1>=ls+1)
			{
				int p=fnd(ls+1);
				while(p<=rb-1)
				{
					g1[x].push_back(p),g1[p].push_back(x);
					q.push(p);
					f[p]=fnd(p+1);
					p=fnd(p);
				}
			}
			ls=rb;
		}
	}
}
void gett()
{
	for(int i=1;i<=n+1;i++)
		f[i]=i;
	for(int i=1;i<=n;i++)
		if(del[i])
			f[fnd(i)]=fnd(i+1);
	for(int i=1;i<=n;i++)
		if(fnd(i)==i)
		{
			// printf("i:%d",i),fflush(stdout);
			tot=0;
			bfs(i);
			for(int j=1;j<=tot;j++)
			{
				int x=st[j];
				if(vis[x])
					continue;
				for(int v:g1[x])
					if(!vis[v])
						vis[v]=x,g2[x].insert(v);
				if(g2[x].empty())
				{
					int v=g1[x][0];
					int rt=vis[v];
					if(rt==v)
						g2[rt].insert(x),vis[x]=rt;
					else if(g2[rt].size()==1)
						g2[rt].clear(),g2[v].insert(rt),g2[v].insert(x),vis[rt]=vis[v]=vis[x]=v;
					else
						g2[rt].erase(v),g2[x].insert(v),vis[v]=vis[x]=x;
				}
			}
		}
	int sm=0;
	// puts("qwq");
	// for(int i=1;i<=n;i++)
	// 	for(int j:g1[i])
	// 		if(i<j)
	// 			printf("%d %d\n",i,j);
	// puts("pwp");
	for(int i=1;i<=n;i++)
		if(g2[i].size())
		{
			// printf("i:%d------------\n",i);
			// for(int v:g2[i])
			// 	printf("%d ",v);
			// printf("\n");
			ansp[i]=sm+1,ansq[i]=sm+g2[i].size()+1;
			int tp=0;
			for(int v:g2[i])
				tp++,ansp[v]=sm+tp+1,ansq[v]=sm+tp;
			sm=ansq[i];
		}
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1,a,b;i<=m;i++)
		{
			scanf("%d%d",&a,&b);
			ql[i]=a,qr[i]=b;
			deg0[a]++,deg0[b]++;
		}
		int tp=n;
		for(int i=1;i<=n;i++)
			if(deg0[i]==n-1)
				ansp[i]=ansq[i]=tp--,del[i]=1;
		for(int i=1;i<=m;i++)
			if(!del[ql[i]]&&!del[qr[i]])
				g0[ql[i]].push_back(qr[i]),g0[qr[i]].push_back(ql[i]);
		for(int i=1;i<=n;i++)
			sort(g0[i].begin(),g0[i].end());
		// printf("qwq");
		gett();
		for(int i=1;i<=n;i++)
		{
			assert(ansp[i]);
			assert(ansq[i]);
		}
		for(int i=1;i<=m;i++)
			assert((ll)(ansp[ql[i]]-ansp[qr[i]])*(ansq[ql[i]]-ansq[qr[i]])>0);
		for(int i=1;i<=n;i++)
			printf("%d ",ansp[i]);
		printf("\n");
		for(int i=1;i<=n;i++)
			printf("%d ",ansq[i]);
		printf("\n");
		clr();
	}
	return 0;
}