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:
#pragma optimize("SEX_ON_THE_BEACH")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("fast-math")
#define _FORTIFY_SOURCE 0 
#pragma GCC optimize("no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native") 
 
 
#include<bits/stdc++.h>
 
using ll = long long int;
using ull = unsigned long long int;
using dd = double;
using ldd = long double;
 
namespace someUsefull {
    template<typename T1, typename T2>
    inline void checkMin(T1& a, T2 b) {
        if (a > b)
            a = b;
    }
 
    template<typename T1, typename T2>
    inline void checkMax(T1& a, T2 b) {
        if (a < b)
            a = b;
    }
 
    const int _bitfunctions_size_ = 16;
    const int _bitfunctions_mask_ = (1 << _bitfunctions_size_) - 1;
    char* _bits_count_;
    
    inline void _build_bits_count_() {
        _bits_count_ = new char[1 << _bitfunctions_size_];
        for (int i = 1; i < (1 << _bitfunctions_size_); ++i) {
            _bits_count_[i] = _bits_count_[i >> 1];
            if (i & 1) ++_bits_count_[i];
        }
    }
 
    template<typename T1 = char, typename T2 = int>
    inline T1 popcnt(T2 x) {
        T1 ans = 0;
        while (x) {
            ans += _bits_count_[x & _bitfunctions_mask_];
            x >>= _bitfunctions_size_;
        }
        return ans;
    }
}
 
namespace operators {
    template<typename T1, typename T2>
    std::istream& operator>>(std::istream& in, std::pair<T1, T2>& x) {
        in >> x.first >> x.second;
        return in;
    }
 
    template<typename T1, typename T2>
    std::ostream& operator<<(std::ostream& out, std::pair<T1, T2> x) {
        out << x.first << " " << x.second;
        return out;
    }
 
    template<typename T1>
    std::istream& operator>>(std::istream& in, std::vector<T1>& x) {
        for (auto& i : x) in >> i;
        return in;
    }
 
    template<typename T1>
    std::ostream& operator<<(std::ostream& out, std::vector<T1>& x) {
        for (auto& i : x) out << i << " ";
        return out;
    }
}
 
//name spaces
using namespace std;
using namespace operators;
using namespace someUsefull;
//end of name spaces
 
//defines
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
 
//end of defines
//#undef HOME
//debug defines
#ifdef HOME
    #define debug(x) cerr << #x << " " << x << endl;
    #define debug_v(x) {cerr << #x << " "; for (auto ioi : x) cerr << ioi << " "; cerr << endl;}
    #define debug_vp(x) {cerr << #x << " "; for (auto ioi : x) cerr << '[' << ioi.ff << " " << ioi.ss << ']'; cerr << endl;}
    #define debug_v_v(x) {cerr << #x << "/*\n"; for (auto ioi : x) { for (auto ioi2 : ioi) cerr << ioi2 << " "; cerr << '\n';} cerr << "*/" << #x << endl;}
    int jjj;
    #define wait() cin >> jjj;
    #define PO cerr << "POMELO" << endl;
    #define OL cerr << "OLIVA" << endl;
    #define gen_clock(x) cerr << "Clock " << #x << " created" << endl; ll x = clock(); 
    #define check_clock(x) cerr << "Time spent in " << #x << ": " << clock() - x << endl; x = clock();
    #define reset_clock(x) x = clock();
    #define say(x) cerr << x << endl;
#else
    #define debug(x) 0;
    #define debug_v(x) 0;
    #define debug_vp(x) 0;
    #define debug_v_v(x) 0;
    #define wait() 0;
    #define PO 0;
    #define OL 0;
    #define gen_clock(x) 0;
    #define check_clock(x) 0;
    #define reset_clock(x) 0;
    #define say(x) 0;
#endif // HOME
 
vector<set<int>> tree;
vector<set<int>> gr;

void solve(int test) {
	tree.clear();
	gr.clear();
	int n, m;
	cin >> n >> m;
	tree.resize(n);
	gr.resize(n);
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		--a;
		--b;
		gr[a].insert(b);
		gr[b].insert(a);
	}
	set<int> can;
	for (int i = 0; i < n; ++i) can.insert(i);
	set<int> bfs;
	while (can.size()) {
		PO;
		bfs.insert(*can.begin());
		can.erase(can.begin());
		while (bfs.size()) {
			int v = *bfs.begin();
			bfs.erase(v);
			for (auto i = can.begin(); i != can.end();) {
				if (gr[v].count(*i)) {i++;continue;}
				int to = *i;
				i++;
				can.erase(to);
				bfs.insert(to);
				tree[v].insert(to);
				tree[to].insert(v);
			}
		}
	}
	vector<int> a(n), b(n);
	int x = 0;
	vector<bool> was(n);
	for (int i = 0; i < n; ++i) {
		if (was[i]) continue;
		OL;
		debug(i);
		PO;
		map<int, int> deg;
		deque<int> bfs;
		bfs.push_back(i);
		while (bfs.size()) {
			int v = bfs.front();
			bfs.pop_front();
			deg[v] = tree[v].size();
			was[v] = 1;
			for (int to : tree[v]) {
				if (!was[to]) {
					was[to] = 1;
					bfs.push_back(to);
				}
			}
		}
		set<pair<int, int>> have;
		for (auto i : deg) {
			have.insert({i.ss, i.ff});
		}
		if (have.size() == 1) {
			a[i] = b[i] = x++;
			continue;
		}

		debug_v_v(tree);
		debug_vp(have);

		while (have.size()) {
			int v = have.begin()->ss;
			int p = *tree[v].begin();
			debug(p);
			have.erase({deg[p], p});
			vector<int> to;
			for (int too : tree[p]) {
				if (deg[too] == 1) to.push_back(too);
				else {
					have.erase({deg[too], too});
					--deg[too];
					have.insert({deg[too], too});
					tree[too].erase(p);
				}
			}
			debug_v(to);
			for (int i : to) have.erase({1, i});
			int ox = x;
			for (int i : to) {
				a[i] = ox;
				b[i] = ++ox;
			}
			debug_v(a);
			debug_v(b);
			a[p] = ox;
			b[p] = x;
			x = ox + 1;
		}
	}
	for (int& i : a) ++i;
	for (int& i : b) ++i;
	cout << a << '\n' << b << '\n';
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
 
    int t = 1;
    cin >> t;
 
    for (int i = 0; i < t; ++i) {
        solve(i + 1);
    }
    return 0;
}