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;

typedef long long ll;

const int INFi = 1e9+67;
const ll INFll = 1e18;

using NumberType = double;

//ll mod = 1e9+7;
ll mod = 998244353;

namespace std {
    template<typename a, typename b>
    struct hash<std::pair<a, b> > {
    public:
        hash() {}
        size_t operator()(const std::pair<a, b> &p) const {
            return hash<a>()(p.first) + hash<b>()(p.second)*998242353;
        }
    };
};

namespace {
    struct None {
        friend bool operator<(const None& lhs, const None& rhs) {
            return false;
        }
    };

    struct Edge {
        int to;
    };

    struct WEdge {
        int to;
        ll w;
    };

#define ParEdgeType typename conditional<is_same<EIdType,None>::value, EType, pair<EIdType, EType>>::type
    template<typename EIdType, typename EType>
    struct PFInfo {
        int par = -1;
        ll dist = INFll;
        ParEdgeType parEdge;

        friend bool operator<(const PFInfo& a, const PFInfo& b) {
            return a.dist<b.dist;
        }

        bool isPath() {
            return dist!=INFll;
        }
    };

#define FOR_GRAPH(ReturnType) template<typename EIdType_=EIdType> \
        typename enable_if<is_same<EIdType_, None>::value, ReturnType>::type
#define FOR_BOR(ReturnType) template<typename EIdType_=EIdType> \
        typename enable_if<!is_same<EIdType_, None>::value, ReturnType>::type

    template<typename VType_, typename EType_, typename VIdType=None, typename EIdType=None>
    struct Graph {
        using VType = VType_;
        using EType = EType_;
        vector<VType> v;
        typename conditional<is_same<EIdType, None>::value, vector<vector<EType>>, vector<map<EIdType, EType>>>::type g;
        vector<PFInfo<EIdType, EType>> pf;

        Graph(int n): v(n), g(n), pf(n) {};
        Graph(): Graph(0) {};

        FOR_GRAPH(void) addOEdge(int u, int v, const EType& newE) {g[u].push_back(newE); g[u].back().to = v;}
        FOR_BOR(void) addOEdge(int u, int v, const EType& newE) {assert(false);}
        FOR_GRAPH(void) addEdge(int u, int v, const EType& newE) {addOEdge(u,v, newE);addOEdge(v,u, newE);}
        FOR_BOR(void) addEdge(int u, int v, const EType& newE) {assert(false);}

        FOR_BOR(void) addOEdge(int u, int v, const EIdType& newEId, const EType& newE) {assert(g[u].count(newEId)==0); g[u][newEId] = newE; g[u][newEId].to = v;}
        FOR_GRAPH(void) addOEdge(int u, int v, const EIdType& newEId, const EType& newE) {assert(false);}

        //to update edge after insertion
        FOR_GRAPH(int) addOEdge(int u, int v) {g[u].emplace_back(); g[u].back().to = v; return ((int) g[u].size())-1;};
        FOR_BOR(int) addOEdge(int u, int v) {assert(false);};

        FOR_BOR(int) goTo(int from, const EIdType& eId, const EType& newE) {
            if (!g[from].count(eId)) {
                int to = g.addV();
                addOEdge(from, to, eId, newE);
            }
            return g[from][eId].to;
        }
        FOR_GRAPH(int) goTo(int from, const EIdType& eId, const EType& newE) {assert(false);}

        int addV() {
            int id = v.size();
            v.emplace_back();
            g.emplace_back();
            pf.emplace_back();
            return id;
        }

        map<VIdType, int> ids; //or unordered_map if better
        vector<VIdType> idsBack;

        //if too slow, use external vertex id generator, but don't forget to allocate graph of required size
        int asV(const VIdType& id) {
            if (!ids.count(id)) {
                ids[id] = addV();
                idsBack.push_back(id);
            }
            return ids[id];
        }
        const VIdType& asLabel(int id) {
            return idsBack[id];
        }

        void printAdj() const {
            for (int i=0;i<g.size();i++) {
                cout << i+1 << ": ";
                for (auto& it: g[i]) {
                    cout << it.to+1 << " ";
                }
                cout << "\n";
            }
            cout << endl;
        }
    };
//contains common algorithm to restore path

    template<typename EIdType, typename EType>
    struct Path {
        vector<int> verts;
        vector<ParEdgeType> edges;
    };

    template<typename EIdType, typename EType>
    Path<EIdType, EType> restorePath(const vector<PFInfo<EIdType, EType>>& pfInfo, int to) {
        vector<int> verts;
        vector<ParEdgeType> edges;
        while (true) {
            verts.push_back(to);
            if (pfInfo[to].par == -1) { //Not found
                return {};
            }
            if (pfInfo[to].par == -2) {
                reverse(verts.begin(), verts.end());
                reverse(edges.begin(), edges.end());
                return {verts, edges};
            }
            edges.push_back(pfInfo[to].parEdge);
            to = pfInfo[to].par;
        }
    }
}

template<typename G1, typename G2>
void dfs(G1& g, G2& spanTree, set<int>& notVis, int v, int p = -1) {
    assert(notVis.count(v));
    notVis.erase(v);
    if (p!=-1) {
        spanTree.addEdge(v, p, {});
    }
    unordered_set<int> neis;
    for (auto& it: g.g[v]) {
        neis.insert(it.to);
    }
    int prevOption = -1;
    while (1) {
        auto it = notVis.upper_bound(prevOption);
        if (it==notVis.end()) break;
        int to = *it;
        if (!neis.count(to)) {
            dfs(g, spanTree, notVis, to, v);
        }
        prevOption = to;
    }
}

struct VertType {
    int starCenter = -1;
    int starSz = 0;
};
void solve() {
    int n,m;
    cin >> n >> m;
    Graph<None, Edge> g(n);
    Graph<VertType, Edge> spanTree(n);

    set<pair<int,int>> degV;
    vector<pair<int,int>> edges;
    for (int i=0;i<m;i++) {
        int li,ri;
        cin >> li >> ri;
        li--; ri--;
        edges.push_back({li,ri});
        g.addEdge(li,ri,{});
    }
    for (int i=0;i<n;i++) {
        degV.insert({g.g[i].size(), i});
    }

    vector<int> p(n, 0), q(n,0);

    set<int> notVis;
    for (int i=0;i<n;i++) {
        notVis.insert(i);
    }
    for (int i=0;i<n;i++) {
        if (!notVis.count(i)) continue;
        dfs(g, spanTree, notVis, i);
    }

    int curBase = 1;
    for (int i=0;i<n;i++) {
        if (spanTree.v[i].starCenter != -1) continue;
        if (spanTree.g[i].empty()) {
            p[i] = q[i] = curBase++;
            continue;
        }
        bool foundNei = false;
        for (auto& it: spanTree.g[i]) {
            int to = it.to;
            if (spanTree.v[to].starCenter == -1) {
                spanTree.v[to].starCenter = spanTree.v[i].starCenter = i;
                spanTree.v[i].starSz = 2;
                foundNei = true;
                break;
            }
        }
        if (foundNei) continue;
        int to = spanTree.g[i][0].to;
        int parTo = spanTree.v[to].starCenter;
        if (to==parTo) {
            spanTree.v[parTo].starSz++;
            spanTree.v[i].starCenter = parTo;
        } else
        if (spanTree.v[parTo].starSz >= 3) {
            spanTree.v[parTo].starSz--;
            spanTree.v[to].starCenter = spanTree.v[i].starCenter = i;
            spanTree.v[i].starSz = 2;
        } else {
            spanTree.v[to].starCenter = spanTree.v[parTo].starCenter = spanTree.v[i].starCenter = to;
            spanTree.v[to].starSz = 3;
        }
    }
    for (int i=0;i<n;i++) {
        if (spanTree.g[i].empty()) {
            continue;
        }
        if (spanTree.v[i].starCenter != i) continue;
        int pVal = curBase;
        int qVal = curBase+1;
        for (auto& it: spanTree.g[i]) {
            int to = it.to;
            if (spanTree.v[to].starCenter != i) continue;
            p[to] = pVal++;
            q[to] = qVal++;
        }
        q[i] = curBase;
        p[i] = pVal;
        curBase = qVal;
    }

    for (int i=0;i<n;i++) {
        cout << p[i] << " ";
    }
    cout << "\n";

    for (int i=0;i<n;i++) {
        cout << q[i] << " ";
    }
    cout << "\n";

}
int main() {

//        freopen("input.txt","w",stdout);
//        int n = 100'000;
//        for (int i=0;i<n;i++) {
//            cout << 1 << " ";
//        }
//        cout << "\n";
//        for (int i=1;i<n;i++) {
//            cout << 1 << " " << i+1 << "\n";
//        }
//        for (int i=0;i<n;i++) {
//            cout << 200'000 << " ";
//        }
    //    cout << 10 << " " << 0 << "\n";
    //    int starsLeft = 5;
    //    for (int i=0;i<10;i++) {
    //        for (int j=0;j<10;j++) {
    //            int kekw = rand() % 20;
    //            if (kekw==1 && starsLeft) {
    //                cout << "*";
    //                starsLeft--;
    //            } else {
    //                cout << ((char) ('0' + (rand() % 10)));
    //            }
    //        }
    //        cout << "\n";
    //    }
//        return 0;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("output.bin","w",stdout);
    //freopen("/tmp/output.txt","w",stdout);
    cout << setprecision(2) << fixed;
    int t;
    cin >> t;
    for (int i=0;i<t;i++)
        //    ll start = clock();
        //    while (1)
        solve();
    //    double time = (clock() - start) * 1.0 / CLOCKS_PER_SEC;
    //    cout<< time << "s.";
    return 0;
}