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 <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;
}