#include<bits/stdc++.h>

#define MAXN 200005

namespace sub1{
    int T,n,m,x,y;
    std::vector<int> g[MAXN];
    int li[MAXN],pos[MAXN];
    int vis[MAXN];
    int uu[MAXN],vv[MAXN];
    bool ok=false;

    void dfs(int lvl){
        if(lvl>n) return (void)(ok=true);
        for(int i=1;i<=n;i++) if(!vis[i]){
            int tag=0;
            li[lvl]=i;
            for(int x:g[i]){
                int y=pos[x]; if(!y) continue;
                for(int j=1;j<=m;j++){
                    if((!pos[uu[j]])||(!pos[vv[j]])) continue;
                    if(pos[uu[j]]<=y&&pos[vv[j]]<=y) continue;
                    if(pos[uu[j]]>=y&&pos[vv[j]]>=y) continue;
                    tag=1; break;
                }
                if(tag) break;
            }
            if(!tag){
                pos[i]=lvl;
                vis[i]=1;
                dfs(lvl+1);
                vis[i]=0;
                pos[i]=0;
            }
            if(ok) return;
        }

        return;
    }
   
    void run(){
        memset(li,0,sizeof(li)),memset(pos,0,sizeof(pos));
        memset(vis,0,sizeof(vis));
        std::cin>>n>>m;
        for(int i=1;i<=n;i++) g[i].clear();
        for(int i=1;i<=m;i++){
            std::cin>>x>>y,g[x].push_back(y),g[y].push_back(x);
            uu[i]=x,vv[i]=y;
        }
        ok=false; dfs(1);
        for(int i=1;i<=n;i++) std::cout<<li[i]<<' ';
        std::cout<<'\n';
        return;
    }
    void main(){
        std::cin>>T; for(int i=1;i<=T;i++) run();
        return;
    }
}

namespace subc{
    int T;
    int n,m,x,y;
    std::vector<int> g[MAXN];
    int nxt[MAXN];
    int vis[MAXN],h[MAXN],t[MAXN];
    int st[MAXN],tp;

    void expand(int u){
        for(int i=u;i;i=nxt[i]){
            while(tp&&st[tp]<i) expand(st[tp--]);
            std::cout<<i<<' ';
        }
        return;
    }
    
    void dfs(int u,int fa){
        vis[u]=1;
        std::vector<int> tmp; tmp.push_back(u);
        for(int v:g[u]){
            if(v==fa) continue;
            dfs(v,u);
            tmp.push_back(v);
        } 
        std::sort(tmp.begin(),tmp.end(),[](int x,int y){ return h[x]<h[y]; });
        for(int i=1;i<tmp.size();i++){
            nxt[t[tmp[i-1]]]=h[tmp[i]];
        }
        h[u]=h[tmp.front()],t[u]=t[tmp.back()];
        return;
    }
    void run(){
        std::cin>>n>>m;
        for(int i=1;i<=n;i++) g[i].clear();
        for(int i=1;i<=n;i++) nxt[i]=0,vis[i]=0,h[i]=t[i]=i;
        for(int i=1;i<=m;i++){
            std::cin>>x>>y;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        tp=0;
        for(int i=1;i<=n;i++){
            if(!vis[i]){
                dfs(i,0);
                st[++tp]=i;
            }
       }
        std::reverse(st+1,st+tp+1);
        while(tp) expand(st[tp--]);
        std::cout<<'\n';
        return;
    }
    void main(){
        std::cin>>T; for(int i=0;i<T;i++) run();
        return;
    }
}

namespace subf{
    int T;
    int n,m,x,y;
    std::vector<int> g[MAXN];
    int nxt[MAXN];
    int vis[MAXN],h[MAXN],t[MAXN];
    int fa[MAXN];
    int st[MAXN],tp;

    void expand(int u){
        for(int i=u;i;i=nxt[i]){
            while(tp&&st[tp]<i) expand(st[tp--]);
            std::cout<<i<<' ';
        }
        return;
    }
    
    void dfs(int u,int fa){
        vis[u]=1;
        std::vector<int> tmp; tmp.push_back(u);
        for(int v:g[u]){
            if(v==fa) continue;
            dfs(v,u);
            tmp.push_back(v);
        } 
        std::sort(tmp.begin(),tmp.end(),[](int x,int y){ return h[x]<h[y]; });
        for(int i=1;i<tmp.size();i++){
            nxt[t[tmp[i-1]]]=h[tmp[i]];
        }
        h[u]=h[tmp.front()],t[u]=t[tmp.back()];
        return;
    }

    int find(int x){ return (x==fa[x])?x:(fa[x]=find(fa[x])); }
    
    void run(){
        std::cin>>n>>m;
        for(int i=1;i<=n;i++) g[i].clear();
        for(int i=1;i<=n;i++) nxt[i]=0,vis[i]=0,h[i]=t[i]=i,fa[i]=i;
        for(int i=1;i<=m;i++){
            std::cin>>x>>y;
            if(find(x)==find(y)) continue;
            g[x].push_back(y);
            g[y].push_back(x);
            fa[find(x)]=find(y);
        }
        tp=0;
        for(int i=1;i<=n;i++){
            if(!vis[i]){
                dfs(i,0);
                st[++tp]=i;
            }
        }
        std::reverse(st+1,st+tp+1);
        while(tp) expand(st[tp--]);
        std::cout<<'\n';
        return;
    }
    void main(){
        std::cin>>T; for(int i=0;i<T;i++) run();
        return;
    }
}

int c;
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0),std::cout.tie(0);

    std::cin>>c;
    if(c==1||c==2) sub1::main();
    else if(c==3||c==4||c==7||c==8||(c>=12&&c<=15)||(c==19||c==20||c==21)) subc::main();
    else subf::main();

    return 0;
}