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 fr(i,n) for(int i = 0; i<n; i++)
#define sz(v) (int)(v.size())
#define prin(a) cout << #a << " = " << a << endl
#define prinv(v) cout << #v << " = "; for(auto it : v) cout << it << ", "; cout << endl
#define all(v) (v).begin(),(v).end()

typedef long long ll;

#define rmin(a,b) a = min<ll>(a,b)
#define rmax(a,b) a = max<ll>(a,b)

#define fi first
#define se second

vector<vector<int>> mataux;
vector<int> ativ;
vector<int> deg;

void dfs(int no, vector<vector<int>> &g){
	assert(deg[no]==1);
	int na = 0;
	mataux.emplace_back();
	int centro;
	for(auto &it : g[no]){
		if(ativ[it]){
			na++;
			mataux.back().push_back(it);
			centro = it;
		}
	}
	assert(na==1);
	mataux.back().emplace_back(no);
	
	ativ[no] = ativ[centro] = 0;
	
	vector<int> v;
	for(auto &it : g[centro]){
		if(ativ[it] and it!=no){
			deg[it]--;
			if(deg[it]==0){
				ativ[it] = 0;
				mataux.back().emplace_back(it);
			} else if(deg[it]==1){
				v.push_back(it);
			}
		}
	}
	for(auto &it : v) dfs(it,g);
}	

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	fr(tt,t){
		int n, m; cin >> n >> m;
		vector<vector<int>> g1(n);
		fr(i,m){
			int l,r; cin >> l >> r; l--,r--;
			g1[l].push_back(r);
			g1[r].push_back(l);
		}
		
		vector<int> ans1(n,-1), ans2(n,-1);
		vector<vector<int>> g2(n);
		int cur_val = 1;
		fr(i,n){
			sort(all(g1[i]));
			if(sz(g1[i])==n-1) ans1[i] = ans2[i] = cur_val++;
			else if(g2[i].empty()){
				fr(j,n){
					if(j!=i and !binary_search(all(g1[i]),j)){
						g2[i].push_back(j);
						g2[j].push_back(i);
						break;
					}
				}
			}
		}
		
		deg = vector<int>(n);
		fr(i,n) deg[i] = sz(g2[i]);
		ativ = vector<int>(n,1);
		
		fr(i,n) if(ans1[i]!=-1) ativ[i] = 0;
		fr(i,n){
			if(ativ[i] and deg[i]==1){
				mataux.clear();
				dfs(i,g2);
				
				for(auto &vaux : mataux){
					assert(sz(vaux)>=2);
					int cur1 = cur_val;
					int curn = cur_val + sz(vaux)-1;
					
					fr(j,sz(vaux)){
						int id = vaux[j];
						if(j==0){
							ans1[id] = cur1;
							ans2[id] = curn;
						} else{
							ans1[id] = cur1+j;
							ans2[id] = cur1+j-1;
						}
					}
					
					cur_val+=sz(vaux);
				}
			}
		}
		
		assert(cur_val==n+1);
		
		fr(i,sz(ans1)){
			if(i) cout << " ";
			cout << ans1[i];
		}		
		cout << "\n";
		fr(i,sz(ans2)){
			if(i) cout << " ";
			cout << ans2[i];
		}		
		cout << "\n";
	}
}