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 DB double
#define LL long long
 
#define MST(a,b) memset((a),(b),sizeof(a))
 
#ifdef _DEBUG_
#define MRK() cout<<"Mark"<<endl;
#define WRT(x) cout<<#x<<" = "<<(x)<<endl;
#else
#define MRK() ;
#define WRT(x) ;
#endif
 
#define MAXN 1010000
#define MAXM 2010000
#define MOD 998244353  //1000000007
#define INF 0x3f3f3f3f
#define LLINF 0x3f3f3f3f3f3f3f3f
#define EPS 1e-5
 
#define _ 0
using namespace std;
 
vector<int> g[MAXN];
int ansp[MAXN],ansq[MAXN]; 
int n,m,x,y,cnt,treecnt;
int deg[MAXN];
vector<int> tree[MAXN];
typedef pair<int,int> pii;
int center[MAXN];
set<int> star[MAXN];
set<pii,greater<pii> > st;
set<int> rev; 
void dfs1(int pos)
{
	int ptr=0;
	rev.erase(pos);
	int p=0;
	while (1)
	{
		auto it=rev.lower_bound(p);
		if (it==rev.end())
			return;
		p=*it;
		auto vit=lower_bound(g[pos].begin(),g[pos].end(),p);
		if (vit!=g[pos].end() && *vit==p)
		{
			p++;
			continue;
		}
		tree[pos].push_back(p);
		tree[p].push_back(pos);
		//cout<<p<<' '<<pos<<endl;
		treecnt++;
		dfs1(p);
	}
}
 
 
void work()
{
	cin>>n>>m;
	st.clear();
	cnt=0;
	treecnt=1;
	for (int i=1;i<=n;i++)
	{
		ansp[i]=ansq[i]=deg[i]=center[i]=0;
		g[i].clear();
		tree[i].clear();
		star[i].clear();
	}
	for (int i=0;i<m;i++)
	{
		scanf("%d%d",&x,&y);
		//cout<<x<<' '<<y<<endl;
		g[x].push_back(y);
		g[y].push_back(x);
		deg[x]++,deg[y]++;
	}
	for (int i=1;i<=n;i++)
		sort(g[i].begin(),g[i].end());
	for (int i=1;i<=n;i++)
	{
		st.insert({deg[i],i});
		//WRT(st.begin()->second);
	}
	cnt=n;
	while (st.begin()->first==cnt-1)
	{
		//for (int i=1;i<=n;i++)
		//	cout<<i<<' '<<deg[i]<<'!'<<endl;
		int pos=st.begin()->second;
		WRT(pos);
		st.erase({deg[pos],pos});
		ansp[pos]=ansq[pos]=cnt;
		cnt--;
		for (auto p:g[pos])
		{
			if (ansp[p])
				continue;
			st.erase({deg[p],p});
			deg[p]--;
			st.insert({deg[p],p});
		}
	}
	WRT(cnt)
	for (int i=1;i<=n;i++)
		if (ansp[i]==0)
			rev.insert(i); 
	for (int i=1;i<=n;i++)
	{
		WRT(i)
		WRT(rev.count(i))
		if (rev.count(i))
		{
			WRT(i);
			dfs1(i);
			//break;
		}
	}
	WRT(treecnt)
	for (int i=1;i<=n;i++)
		if (deg[i]<cnt-1)
		{
			if (center[i]==0)
			{
				WRT(i)
				for (auto p:tree[i])
					if (center[p]==p)
					{
						center[i]=p;
						star[p].insert(i);
						break;
					}
				WRT(i)
				if (center[i])
					continue; 
				center[i]=i;
				for (auto p:tree[i])
					if (center[p]==0)
					{
						center[p]=i;
						star[i].insert(p);
					}
				if (star[i].size()==0)
				{
					int to=tree[i][0];
					if (star[center[to]].size()>=2)
					{
						star[center[to]].erase(to);
						star[i].insert(to);
						center[to]=i;
					}
					else
					{
						WRT(to)
						WRT(i)
						WRT(center[to])
						star[center[to]].erase(to);
						star[to].insert(center[to]);
						star[to].insert(i);
						center[center[to]]=center[i]=to;
						center[to]=to;
						MRK();
					}
						
				}
			}
		}
	MRK();
	int tmp=1;
	for (int i=1;i<=n;i++)
		if (star[i].size())
		{
			WRT(i);
			for (auto p:star[i])
				WRT(p);
			ansp[i]=tmp;
			ansq[i]=tmp+star[i].size();
			tmp++;
			for (auto p:star[i])
			{
				ansp[p]=tmp;
				ansq[p]=tmp-1;
				tmp++;
			}
		}
	for (int i=1;i<=n;i++)
		printf("%d ",ansp[i]);
	putchar('\n');
	for (int i=1;i<=n;i++)
		printf("%d ",ansq[i]);
	putchar('\n');
}
 
int main()
{
	#ifdef _DEBUG_
	freopen("C:/Users/DELL/Documents/Dev-C++/sample.in","r",stdin);
	#endif
	int casenum=1;
	scanf("%d",&casenum);
	for (int testcase=1;testcase<=casenum;testcase++)
	{
		#ifdef _DEBUG_
		printf("Case #%d:\n",testcase);
		#endif
		work();
	}
	return ~~(0^_^0);
}