#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<map>
#include<utility>
#include<vector>
#include<stack>
#include<queue>
//#define int long long
typedef long long ll;
using namespace std;
int to[1200010],nxt[1200010],head[1200010],cnt;
void add(int a,int b){
    to[++cnt]=b;
    nxt[cnt]=head[a];
    head[a]=cnt;
}
int dfn[400010],low[400010],dfc,vis[400010];
int ptf[400010],ptc,n,m,htl[400010],msk[400010],dti[400010];
vector<int> rtl,ptl[400010],rtr[400010];
stack<int> st;
void tj(int u){
    dfn[u]=low[u]=++dfc;
    vis[u]=1;
    st.push(u);
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(!dfn[v]){
            tj(v),low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                ptc++;
                ptf[ptc]=u;
                while(1){
                    int y=st.top();
                    add(n+y,2*n+ptc);
                    add(2*n+ptc,n+y);
                    if(y==u)break;
                    st.pop();
                }
            }
        }
        else if(vis[v])low[u]=min(low[u],dfn[v]);
    }
}
//deque<int> q;
void ord(int k){
    //while(!q.empty())q.pop_back();
    ptl[k].push_back(ptf[k]);
    for(int i=head[2*n+k];i;i=nxt[i])if(to[i]!=ptf[k]+n)ptl[k].push_back(to[i]-n);
    ////////////////////////////////////////////////////////////////////////////////////////////////////
}
void dh(int u,int p){
    dti[u]=u;
    for(int i=head[u+n];i;i=nxt[i]){
        int q=to[i]-2*n;
        if(q!=p){
            for(int j=1;j<ptl[q].size();j++){
                dh(ptl[q][j],q);
                if(j==1||j==ptl[q].size()-1)dti[u]=min(dti[u],dti[ptl[q][j]]);
            }
        }
    }
}
int cmp(int p,int q){
    return min(dti[ptl[p][1]],dti[ptl[p][ptl[p].size()-1]])<min(dti[ptl[q][1]],dti[ptl[q][ptl[q].size()-1]]);
}
void dfs(int u,int p,int id){
    if(msk[u])rtr[id].push_back(u),msk[u]=0,htl[u]=1;
    vector<int> tmp;
    tmp.push_back(0);
    int cnt=0;
    for(int i=head[u+n];i;i=nxt[i]){
        int q=to[i]-2*n;
        if(q!=p)tmp.push_back(q),cnt++;
    }
    sort(tmp.begin()+1,tmp.end(),cmp);
    for(int i=1;i<=cnt;i++){
        int q=tmp[i];
        if(u<min(dti[ptl[q][1]],dti[ptl[q][ptl[q].size()-1]]))if(!htl[u])rtr[id].push_back(u),htl[u]=1;
        if(dti[ptl[q][1]]<dti[ptl[q][ptl[q].size()-1]])for(int i=1;i<ptl[q].size();i++){
            msk[dti[ptl[q][i]]]=1;
            dfs(ptl[q][i],q,id);
        }else for(int i=ptl[q].size()-1;i>=1;i--){
            msk[dti[ptl[q][i]]]=1;
            dfs(ptl[q][i],q,id);
        }
    }
    if(!htl[u])rtr[id].push_back(u),htl[u]=1;
}
int tbl[400010];
priority_queue<int,vector<int>,greater<int> > pq;
void dfs2(int i,int cm){
    for(int j=0;j<rtr[i].size();j++){
        cout<<rtr[i][j]<<" ";
        while(j==rtr[i].size()-1&&!pq.empty()&&cm>pq.top()||!pq.empty()&&j<rtr[i].size()-1&&rtr[i][j+1]>pq.top()){
            int h=tbl[pq.top()];
            pq.pop();
            dfs2(h,(j==rtr[i].size()-1)?cm:min(cm,rtr[i][j+1]));
        }
    }
}
void mian(){
    cin>>n>>m;
    for(int i=1;i<=3*n;i++)head[i]=0;
    cnt=0;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfc=ptc=0;
    for(int i=0;i<=n;i++)dfn[i]=low[i]=ptf[i]=vis[i]=htl[i]=msk[i]=tbl[i]=0,dti[i]=0x3f3f3f3f,ptl[i].clear(),rtr[i].clear();
    rtl.clear();
    for(int i=1;i<=n;i++)if(!dfn[i]){
        rtl.push_back(i);
        tj(i);
        while(!st.empty())vis[st.top()]=0,st.pop();
    }
    for(int i=1;i<=ptc;i++)ord(i);
    //for(int i=1;i<=ptc;i++){
        //cout<<i<<endl;
        //for(int j=0;j<ptl[i].size();j++)cout<<ptl[i][j]<<" ";
        //cout<<endl;
    //}
    for(int i=0;i<rtl.size();i++){
        int u=rtl[i];
        tbl[u]=i;
        dh(u,0);
        msk[u]=1;
        dfs(u,0,i);
        //cout<<"Q";
        //for(int j=0;j<rtr[i].size();j++)cout<<rtr[i][j]<<" ";
        //cout<<endl;
    }
    for(int i=1;i<rtl.size();i++)pq.push(rtl[i]);
    dfs2(0,0x3f3f3f3f);
    cout<<endl;
}
signed main(){
    freopen("graperm.in","r",stdin);
    freopen("graperm.out","w",stdout);
    int c,T;
    cin>>c>>T;
    for(int I=1;I<=T;I++)mian();
    return 0;
}