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:
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 500002;

int t;

int n, m;

set <int> edges[N_MAX];

set <int> notVisited;

vector <int> treeEdges[N_MAX];

void dfs (int u)
{
    notVisited.erase(u);
    int v = 0;
    while(true)
    {
        set <int> :: iterator it = notVisited.upper_bound(v);
        if(it == notVisited.end())
            break;
        v = *it;
        if(edges[u].find(v) == edges[u].end())
        {
            treeEdges[u].push_back(v);
            treeEdges[v].push_back(u);
            dfs(v);
        }
    }
}

int ansp[N_MAX], ansq[N_MAX];

bool inStar[N_MAX];

int cntSons[N_MAX];
int parent[N_MAX];

vector <int> sons[N_MAX];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t--)
    {
        cin >> n >> m;
        for(int i = 1; i <= m; i++)
        {
            int u, v;
            cin >> u >> v;
            edges[u].insert(v);
            edges[v].insert(u);
        }
        for(int u = 1; u <= n; u++)
            notVisited.insert(u);
        while(notVisited.empty() == false)
            dfs(*notVisited.begin());
        for(int u = 1; u <= n; u++)
        {
            inStar[u] = false;
            cntSons[u] = 0;
            parent[u] = -1;
        }
        int currLast = n;
        for(int u = 1; u <= n; u++)
            if(treeEdges[u].size() == 0)
                ansp[u] = ansq[u] = currLast--;
            else if(inStar[u] == false)
            {
                inStar[u] = true;
                for(int v : treeEdges[u])
                    if(inStar[v] == false)
                    {
                        cntSons[u]++;
                        parent[v] = u;
                        inStar[v] = true;
                    }
                if(cntSons[u] > 0)
                    continue;
                for(int v : treeEdges[u])
                {
                    int w = parent[v];
                    if(cntSons[w] > 1)
                    {
                        parent[v] = u;
                        cntSons[w]--;
                        cntSons[u] = 1;
                        break;
                    }
                }
                if(cntSons[u] > 0)
                    continue;
                int v = treeEdges[u].front();
                int w = parent[v];
                cntSons[w] = 0;
                parent[w] = parent[u] = v;
                cntSons[v] = 2;
                parent[v] = -1;
            }
        for(int u = 1; u <= n; u++)
            if(inStar[u] == true && parent[u] != -1)
                sons[parent[u]].push_back(u);
        int currFirst = 1;
        for(int u = 1; u <= n; u++)
            if(inStar[u] == true && parent[u] == -1)
            {
                ansp[u] = currFirst;
                ansq[u] = currFirst + (int)sons[u].size();
                int curr = currFirst;
                for(int v : sons[u])
                {
                    ansq[v] = curr;
                    curr++;
                    ansp[v] = curr;
                }
                currFirst += (int)sons[u].size() + 1;
            }
        for(int i = 1; i <= n; i++)
            cout << ansp[i] << " ";
        cout << "\n";
        for(int i = 1; i <= n; i++)
            cout << ansq[i] << " ";
        cout << "\n";
        for(int i = 1; i <= n; i++)
        {
            edges[i].clear();
            treeEdges[i].clear();
            sons[i].clear();
        }
    }
    return 0;
}