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:
/*
    ___                         ______      __                  __
   /   |____  __  ___________ _/ ____/___ _/ /___  ____  ______/ /____
  / /| /_  / / / / / ___/ __ `/ /   / __ `/ __/ / / / / / / __  / ___/
 / ___ |/ /_/ /_/ (__  ) /_/ / /___/ /_/ / /_/ /_/ / /_/ / /_/ (__  )
/_/  |_/___/\__,_/____/\__,_/\____/\__,_/\__/\__, /\__, /\__,_/____/
                                            /____//____/

　　　　　／＞　 フ
　　　　　| 　_　 _|
　 　　　／`ミ _x 彡
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

*/

#include <queue>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MP make_pair
#define ll long long
#define fi first
#define se second
using namespace std;

template <typename T>
void read(T &x) {
    x = 0; bool f = 0;
    char c = getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=1;
    for (;isdigit(c);c=getchar()) x=x*10+(c^48);
    if (f) x=-x;
}

template<typename F>
inline void write(F x, char ed = '\n') {
	static short st[30];short tp=0;
	if(x<0) putchar('-'),x=-x;
	do st[++tp]=x%10,x/=10; while(x);
	while(tp) putchar('0'|st[tp--]);
	putchar(ed);
}

template <typename T>
inline void Mx(T &x, T y) { x < y && (x = y); }

template <typename T>
inline void Mn(T &x, T y) { x > y && (x = y); }

#include <set>
const int N = 505000;
set<int> ed[N], S[N];
int id[N], rt[N], p[N], q[N], T, m, n;
void work(void) {
	read(n), read(m);
	for (int i = 1;i <= n; ++i) ed[i].clear(), id[i] = 0;
	for (int i = 1, x, y;i <= m; ++i)
		read(x), read(y), ed[x].insert(y), ed[y].insert(x);
	int all = 0, cnt = 0;
	for (int i = 1;i <= n; ++i) {
		if (ed[i].size() == n - 1) { p[i] = q[i] = ++all; continue; }
		if (id[i]) continue;
		int to = 1;
		ed[i].insert(n + 1);
		for (auto y : ed[i]) { 
			if (i == to) ++to;
			if (y != to) break; 
			++to; 
		}
//		write(to, ' ');
		auto mk = [&](int x, int y) {
			rt[id[x] = id[y] = ++cnt] = x;
			S[cnt].insert(x), S[cnt].insert(y);
		};
		if (!id[to]) { mk(i, to); continue; }
		int ak = id[to];
		if (S[ak].size() == 2 || rt[ak] == to) S[ak].insert(i), rt[id[i] = ak] = to;
		else S[ak].erase(to), mk(i, to);
	}
//	puts("");
	for (int i = 1;i <= cnt; ++i) {
		p[rt[i]] = ++all;
		for (auto t: S[i]) 
			if (t != rt[i]) q[t] = all, p[t] = ++all;
		q[rt[i]] = all, S[i].clear(), rt[i] = 0;
	}
	for (int i = 1;i <= n; ++i) write(p[i], " \n"[i == n]);
	for (int i = 1;i <= n; ++i) write(q[i], " \n"[i == n]);
}

int main() {
//	freopen ("hs.in","r",stdin); 
	for (read(T); T; T--) work();
	return 0;
}

/*

1
12 31
9 3
8 9
11 1
10 6
7 10
5 2
11 2
12 2
9 11
4 3
11 4
10 4
1 6
3 7
1 12
11 10
1 9
7 6
2 7
1 8
3 5
1 3
7 8
2 6
3 12
1 7
11 6
12 9
4 6
5 4
12 4

*/