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 ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)

int const N = 500000;
int lst[N + 1], n, m, p[N + 1], q[N + 1], fr[N + 1], pa[N + 1], zp[N + 1];
vector<int> gr[N + 1], g[N + 1];
queue<int> qu;

int P(int v) { return zp[v] ? zp[v] = P(zp[v]) : v; }

void solve(){
	scanf("%d%d", &n, &m);
	f(i, 1, n + 1){
		gr[i].clear();
		g[i].clear();
		fr[i] = 0;
		pa[i] = 0;
		zp[i] = 0;
	}
	
	f(i, 0, m){
		int a, b;
		scanf("%d%d", &a, &b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	int z = n;
	f(i, 1, n + 1)if ((int)g[i].size() + 1 == n){
		p[i] = q[i] = z--;
		fr[i] = -1;
	}else {
		sort(g[i].begin(), g[i].end());
		f(j, 0, g[i].size()){
			int t = j + 1;
			if (t >= i)++t;
			if (g[i][j] != t){
				pa[i] = t;
				break;
			}
		}
		if (pa[i] == 0){
			pa[i] = g[i].size() + 1;
			if (pa[i] >= i)++pa[i];
		}
		
		int z = P(pa[i]);
		if (P(i) == z){
			pa[i] = 0;
			continue;
		}else {
			zp[i] = z;
		}
		
		++fr[pa[i]];
	}
	
	f(i, 1, n + 1)if (fr[i] == 0)qu.push(i);
	while (!qu.empty()){
		int v = qu.front();
		qu.pop();
		if (gr[v].empty()){
			if (pa[v])gr[pa[v]].push_back(v);
			else gr[lst[v]].push_back(v);
		}else {
			gr[v].push_back(v);
			reverse(gr[v].begin(), gr[v].end());
			lst[pa[v]] = v;
		}
		
		if (pa[v] && --fr[pa[v]] == 0)qu.push(pa[v]);
	}
	
	f(v, 1, n + 1)if (!gr[v].empty()){
		f(j, 0, gr[v].size())p[gr[v][j]] = z - j;
		f(j, 1, gr[v].size())q[gr[v][j]] = z - j + 1;
		z -= gr[v].size();
		q[v] = z + 1;
	}
	
	f(i, 1, n + 1)printf("%d%c", p[i], i == n ? '\n' : ' ');
	f(i, 1, n + 1)printf("%d%c", q[i], i == n ? '\n' : ' ');
}

int main(){
	int t;
	scanf("%d", &t);
	while (t--)solve();
}