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 N 500010
#define pii pair<int, int>

int t, n, m, l[N], r[N], p[N], q[N], k, centre[N];
set<int> good, leaf[N];
set<int> nei[N];
set<pii> alv;
int use[N];

void assign() {
    for(int u : good) if(!use[u]) {
        set<int> x = good;
        set<int> y;
        for(int v : nei[u]) x.erase(v);
        x.erase(u);
        for(int v : x) if(!use[v]) y.insert(v);
        if(!y.empty()) {
            use[u] = 1;
            for(int v : y) use[v] = 2, leaf[u].insert(v), centre[v] = u;
        }
        else {
            int v = *x.begin();
            int w = centre[v];
            if(leaf[w].size() >= 2) {
                leaf[w].erase(v);
                leaf[u].insert(v);
                use[u] = 1;
                centre[v] = u;
            }
            else {
                leaf[w].clear();
                use[v] = 1, use[w] = use[u] = 2;
                leaf[v].insert(w), leaf[v].insert(u);
                centre[u] = centre[w] = v;
            }
        }
    }
    int l = 1;
    for(int u : good) if(use[u] == 1) {
        p[u] = l ++;
        for(int v : leaf[u]) p[v] = l ++, q[v] = p[v] - 1;
        q[u] = l - 1;
    }
}

int main() {
    for(scanf("%d", &t); t --; ) {
        scanf("%d%d", &n, &m);
        k = n;
        good.clear();
        alv.clear();
        for(int i = 1; i <= n; i ++) nei[i].clear(), good.insert(i), use[i] = 0, leaf[i].clear(), centre[i] = 0;
        while(m --) {
            int u, v;
            scanf("%d%d", &u, &v);
            nei[u].insert(v);
            nei[v].insert(u);
        }
        for(int i = 1; i <= n; i ++) alv.emplace(nei[i].size(), i);
        while(k) {
            pii x = *alv.rbegin();
            if(x.first < k - 1) break;
            alv.erase(x);
            int u = x.second;
            p[u] = q[u] = k --;
            good.erase(u);
            for(int v : nei[u]) alv.erase(pii(nei[v].size(), v)), nei[v].erase(u), alv.emplace(nei[v].size(), v);
        }
        assign();
        for(int i = 1; i <= n; i ++) printf("%d%c", p[i], " \n"[i == n]);
        for(int i = 1; i <= n; i ++) printf("%d%c", q[i], " \n"[i == n]);
    }
}