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 ll long long
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define fors(i, a, b) for(int i = (a); i < (b); ++i)
#define all(vec) vec.begin(),vec.end()
using namespace std;
const int maxn = 5e5 + 5;
int fa[maxn];
int fnd(int x){return x==fa[x]?x:fa[x]=fnd(fa[x]);}
void link(int x,int y){fa[fnd(x)]=fnd(y);}
vector<int> g[maxn],G[maxn];
int n, m;
void init(){
    scanf("%d%d",&n,&m);fors(i,1,n+1) g[i].clear(),G[i].clear();
    while(m--){
        int u,v;scanf("%d%d",&u,&v);
        g[u].pb(v);g[v].pb(u);
    }
}
vector<int> f[maxn];
int a[maxn],p[maxn],q[maxn];
void dfs(int u,int pa){
    for(int v:G[u]){
        if(v==pa) continue; dfs(v, u);
        if(!a[v]) f[u].pb(v), a[v]=1;
    }if(f[u].size()) a[u]=1;
    if(a[u]==0&&u==pa&&G[u].size()) f[G[u][0]].pb(u), a[u]=1;
}
void sol(){
    fors(i,1,n+1) sort(all(g[i])), fa[i]=i, f[i].clear(),a[i]=0;
    fors(i,1,n+1){
        int pre=0, x = 0; g[i].pb(n+1);
        for(int v:g[i]){
            int ok = 0;
            fors(j,pre+1,v){
                if(j==i) continue;
                ok=1;x=j;break;
            }if(ok) break; pre = v;
        }if(x && fnd(x)!=fnd(i)){link(x,i);G[i].pb(x);G[x].pb(i);}
    }
    fors(i,1,n+1) if(!a[i]) dfs(i,i);
    int cur = 1;
    fors(i,1,n+1){
        if(!a[i]) p[i]=q[i]=cur,cur++;
        else if(f[i].size()){
            int sz = f[i].size();
            p[i] = cur, q[i]=cur+sz;
            fors(j,0,f[i].size()){
                int v = f[i][j];
                p[v]=cur+1+j; q[v]=cur+j;
            }cur += sz+1;
        }
    }
    fors(i,1,n+1) printf("%d ",q[i]);puts("");
    fors(i,1,n+1) printf("%d ",p[i]);puts("");
}
int main()
{
    int T;cin>>T;
    while(T--){
        init(); sol();
    }
	return 0;
}