#include <bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
#define pii pair<int,int>
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define pb push_back
const int inf=0x3f3f3f3f;
const int mod=998244353;
int n,m,op,p[100010],q[100010],nxt[100010],k,rt[100010],id[100010],tail[100010];
int ui[200010],vi[200010];
vector<int>g[100010];
int mn[100010],sz[100010];
void dfs(int u,int f)
{
//    cout<<"!   "<<u<<" "<<f<<endl;
    mn[u]=u,sz[u]=1;
    for(auto v:g[u])
        if(v!=f)
        {
            dfs(v,u);
            if(mn[v]<mn[u])mn[u]=mn[v];
            sz[u]+=sz[v];
        }
}
void dfs2(int u,int f,int pos)
{
    vector<pii>tmp;
    for(auto v:g[u])
        if(v!=f&&mn[v]<u)
            tmp.pb({mn[v],v});
    sort(tmp.begin(),tmp.end());
    for(auto x:tmp)
    {
        int v=x.sec;
        dfs2(v,u,pos);
        pos+=sz[v];
    }
    p[++pos]=u;
    tmp.clear();
    for(auto v:g[u])
        if(v!=f&&mn[v]>u)
            tmp.pb({mn[v],v});
    sort(tmp.begin(),tmp.end());
    for(auto x:tmp)
    {
        int v=x.sec;
        dfs2(v,u,pos);
        pos+=sz[v];
    }
}
void solve1()//tree
{
    dfs(1,0);
    dfs2(1,0,0);
    for(int i=1;i<=n;i++)printf("%d ",p[i]);
    printf("\n");
}
set<int>s;
void solve()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)g[i].clear();
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d %d",&u,&v);
        ui[i]=u,vi[i]=v;
        g[u].pb(v),g[v].pb(u);
    }
//    cout<<"dffdfgfg"<<endl;
    if(op<=2&&n<=10)
    {
        for(int i=1;i<=n;i++)p[i]=i;
        do
        {
            bool flag=1;
            for(int i=1;i<=n;i++)q[p[i]]=i;
            for(int i=1;i<=m&&flag;i++)
                for(int j=i+1;j<=m;j++)
                {
                    int u1=ui[i],v1=vi[i],u2=ui[j],v2=vi[j];
                    if(q[u1]>q[v1])swap(u1,v1);
                    if(q[u2]>q[v2])swap(u2,v2);
                    if(q[u1]>q[u2])swap(u1,u2),swap(v1,v2);
                    if(q[u1]<q[u2]&&q[u2]<q[v1]&&q[v1]<q[v2])
                    {
                        flag=0;
                        break;
                    }
                }
            if(flag)break;
        }while(next_permutation(p+1,p+n+1));
        for(int i=1;i<=n;i++)printf("%d ",p[i]);
        printf("\n");
        return;
    }
    bool A=(op>=3&&op<=6)||(op>=12&&op<=18);
    bool B=(op==12);
    bool C=(op>=3&&op<=4)||(op>=7&&op<=8)||(op>=12&&op<=15)||(op>=19&&op<=21);
    if(A&&C)//tree
    {
        solve1();
        return;
    }
    else if(/*C*/1)//forest(hope can pass some tests without C)
    {
        int pos=0;k=0;
        for(int i=1;i<=n;i++)sz[i]=p[i]=q[i]=nxt[i]=rt[i]=id[i]=tail[i]=0;
        for(int i=1;i<=n;i++)
            if(!sz[i])
            {
//                cout<<"!   i="<<i<<endl;
                dfs(i,0);
                dfs2(i,0,pos);
//                cout<<"!pos="<<pos<<endl;
                rt[++k]=pos+1;
                for(int j=pos+1;j<pos+sz[i];j++)nxt[p[j]]=p[j+1],id[p[j]]=k;
                tail[k]=p[pos+sz[i]];
                id[tail[k]]=k;
                pos+=sz[i];
            }
        for(int i=1;i<=n;i++)swap(p[i],q[i]);
//        for(int i=1;i<=n;i++)cout<<q[i]<<" ";
//        cout<<endl;
        s.clear();
        for(int i=1;i<=k;i++)s.insert(q[rt[i]]);
        for(int i=1;i<=n;i++)
        {
//            cout<<"("<<i<<")"<<endl;
//            for(auto x:s)cout<<x<<" ";
//            cout<<endl;
            int u=*s.begin();
            s.erase(u);
//            cout<<"(i="<<i<<" "<<u<<")\n";
//            for(int j=1;j<=n;j++)cout<<nxt[j]<<" ";
//            cout<<endl;
            p[i]=u;
            if(i>1&&u!=nxt[p[i-1]])
            {
                int v=nxt[p[i-1]];
//                cout<<"!"<<u<<"->"<<v<<"     "<<id[u]<<" "<<tail[id[u]]<<endl;
                nxt[tail[id[u]]]=v;
                s.erase(v);
            }
            if(nxt[u])s.insert(nxt[u]);
        }
        for(int i=1;i<=n;i++)printf("%d ",p[i]);
        printf("\n");
    }
}
signed main()
{
//    freopen("graperm8.in","r",stdin);
    freopen("graperm.in","r",stdin);
    freopen("graperm.out","w",stdout);
    int t;
    scanf("%d %d",&op,&t);
    while(t--)solve();
    return 0;
}
/*
7 1
10 8
1 4
1 8
1 10
10 7
7 2
3 6
6 9
6 8

g++ -static -O2 -std=c++14 -Wall graperm.cpp graperm
*/