#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <ostream>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>

using namespace std;

#ifdef _DEBUG
#define DEB 1
#else
#define DEB 0
#endif
#define MTEST() \
  int _t;       \
  cin >> _t;    \
  for (int _tn = 0; _tn < _t; ++_tn)
#define ALL(c) c.begin(), c.end()
#define SZ(c) (int)c.size()

const int N = DEB ? 100 : 5e5 + 7;

int n, m;
vector<int> g[N];
set<int> star[N];
int leader[N];
int p[N];
int q[N];

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  MTEST() {
    cin >> n >> m;
    for (int v = 0; v < n; ++v) {
      g[v].clear();
      star[v].clear();
    }
    for (int i = 0; i < m; ++i) {
      int v, u;
      cin >> v >> u;
      --v, --u;
      g[v].push_back(u);
      g[u].push_back(v);
    }
    int bad_cnt = 0;
    for (int v = 0; v < n; ++v) {
      if (g[v].size() == n - 1) {
        p[v] = q[v] = n - 1 - bad_cnt;
        ++bad_cnt;
      }
    }
    set<int> r;
    for (int v = 0; v < n; ++v) {
      if (g[v].size() != n - 1) {
        r.insert(v);
      }
    }
    for (int v = 0; v < n; ++v) {
      if (g[v].size() != n - 1 && r.count(v)) {
        r.erase(v);
        vector<int> kek;
        for (int u : g[v]) {
          if (g[u].size() != n - 1) {
            if (r.count(u)) {
              kek.push_back(u);
              r.erase(u);
            }
          }
        }
        if (r.empty()) {
          for (int u : kek) {
            r.insert(u);
          }
          set<int> mex(g[v].begin(), g[v].end());
          mex.insert(v);
          int u = 0;
          while (mex.count(u)) {
            ++u;
          }
          r.erase(u);
          if (star[leader[u]].size() >= 2) {
            star[leader[u]].erase(u);
            leader[u] = v;
            star[v].insert(u);
          } else {
            leader[leader[u]] = u;
            leader[v] = u;
            star[leader[u]].clear();
            star[u].insert(v);
            star[u].insert(leader[u]);
          }
        } else {
          for (int u : r) {
            star[v].insert(u);
            leader[u] = v;
          }
          r.clear();
          for (int u : kek) {
            r.insert(u);
          }
        }
      }
    }
    int cur = 0;
    for (int v = 0; v < n; ++v) {
      if (!star[v].empty()) {
        p[v] = cur;
        q[v] = cur + star[v].size();
        ++cur;
        for (int u : star[v]) {
          p[u] = cur;
          q[u] = cur - 1;
          ++cur;
        }
      }
    }
    for (int i = 0; i < n; ++i) {
      cout << p[i] + 1 << ' ';
    }
    cout << '\n';
    for (int i = 0; i < n; ++i) {
      cout << q[i] + 1 << ' ';
    }
    cout << '\n';
  }
  return 0;
}