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>
#define PB push_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define i2 array<int,2>
using namespace std;
const int N = 500100;
const int M = 500100;
set<i2> st;
vector<int> g[N], gr[N], edg[N];
int n, m, U[M], V[M], deg[N], lst, P[N], Q[N], cen, glob;
bool bad[N], used[N];

int get_op(int nm, int v){
    return (U[nm] == v ? V[nm] : U[nm]);
}

void add_new(int v, int u){
    gr[v].PB(u);
    gr[u].PB(v);
}

void get_stars(int v, int p){
    used[v] = 1;

    for (int u : gr[v]){
        if (u == p) continue;

        get_stars(u, v);
    }

    if (sz(edg[v]) == 0){
        if (p < 0){
            for (int u : gr[v]){
                if (u == p) continue;

                edg[v].PB(u);
                edg[u].PB(v);

                return;
            }
        } else {
            edg[v].PB(p);
            edg[p].PB(v);
        }
    }
}

void get_star(int v, int p){
    used[v] = 1;

    if (cen < 0 || sz(edg[cen]) < sz(edg[v]))
        cen = v;

    for (int u : edg[v]){
        if (u == p) continue;

        get_star(u, v);
    }
}

bool cmp(int _x, int _y){
    int fi = get_op(_x, glob);
    int se = get_op(_y, glob);

    return (fi < se);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    int qq; cin >> qq;

    for (; qq; qq--){
        cin >> n >> m;

        for (int i = 0; i < n; i++){
            edg[i].clear();
            g[i].clear();
            gr[i].clear();
            used[i] = 0;
            deg[i] = 0;
            bad[i] = 0;
        }

        for (int i = 0; i < m; i++){
            cin >> U[i] >> V[i]; U[i]--; V[i]--;

            deg[U[i]]++;
            deg[V[i]]++;

            g[U[i]].PB(i);
            g[V[i]].PB(i);
        }

        lst = n;

        st.clear();

        for (int i = 0; i < n; i++)
            st.insert({deg[i], i});

        int siz = n;

        while (sz(st) > 0){
            i2 cur = (*(--st.end()));

            if (siz != cur[0] + 1) break;

            siz--;

            st.erase(cur);

            int v = cur[1];

            bad[v] = 1;

            P[v] = Q[v] = lst--;

            for (int nm : g[v]){
                int u = get_op(nm, v);

                if (bad[u]) continue;

                st.erase({deg[u], u});

                deg[u]--;

                st.insert({deg[u], u});
            }
        }

        if (siz > 0){
            for (int v = 0; v < n; v++){
                if (bad[v]) continue;

                if (sz(gr[v]) > 0) continue;

                if (sz(g[v]) == 0){
                    int beg = 0;

                    while (beg == v) beg++;

                    add_new(beg, v);

                    continue;
                }

                glob = v;

                sort(all(g[v]), cmp);

                // beg end

                if (get_op(g[v][0], v) > 0) {
                    int beg = get_op(g[v][0], v) - 1;

                    while (beg >= 0){
                        if (beg != v) {
                            add_new(beg, v);
                            break;
                        }

                        beg--;
                    }
                }

                if (sz(gr[v]) == 0 && get_op(g[v].back(), v) < n - 1) {
                    int beg = get_op(g[v].back(), v) + 1;

                    while (beg < n){
                        if (beg != v){
                            add_new(beg, v);
                            break;
                        }

                        beg++;
                    }
                }

                if (sz(gr[v]) == 0){
                    for (int it = 1; it < sz(g[v]); it++){
                        int fi = get_op(g[v][it - 1], v);
                        int se = get_op(g[v][it - 0], v);

                        int beg = fi + 1;

                        while (beg < se){
                            if (beg != v){
                                add_new(beg, v);
                                break;
                            }
                            beg++;
                        }

                        if (sz(gr[v]) > 0) break;
                    }
                }

                assert(sz(gr[v]) > 0);
            }

            for (int v = 0; v < n; v++){
                if (used[v] || bad[v]) continue;

                get_stars(v, -1);
            }

            fill(used, used + n, 0);

            for (int v = 0; v < n; v++){
                if (used[v] || bad[v]) continue;

                cen = -1;

                get_star(v, -1);

                assert(cen >= 0);

                int siz = sz(edg[cen]) + 1;

                assert(siz > 1);

                P[cen] = lst;
                Q[cen] = lst - siz + 1;

                for (int u : edg[cen]){
                    lst--;

                    P[u] = lst;
                    Q[u] = lst + 1;
                }

                lst--;
            }
        }

        assert(lst == 0);

        for (int i = 0; i < n; i++)
            cout << P[i] << " "; cout << '\n';
        for (int i = 0; i < n; i++)
            cout << Q[i] << " "; cout << '\n';

        for (int i = 0; i < m; i++){
            int u = U[i], v = V[i];

            if ((P[u] > P[v]) && (Q[u] > Q[v])) continue;
            if ((P[u] < P[v]) && (Q[u] < Q[v])) continue;

            return -1;
        }
    }

    return 0;
}