#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define vi vector<int>
#define inf 0x3f3f3f3f
using namespace std;
const int N=5e5+5;
int T,n,m,du[N],cnt[N],vs[N],to[N],vs0[N];
struct node{
    int u,v;
}q[N];
struct node0{
    int u,v,i;
};
mt19937 gen(time(0));
vector<int>pos[N];
vector<int>v1,v2,v3,st;
vector<node0>vec;
int get(int u,int i=0){
    int j=0;
    while(vs[pos[u][j]]||pos[u][j]==i)j++;
    return pos[u][j];
}
bool check(int u,int i){
    if(du[u]==1)return 0;
    if(du[u]>2)return 1;
    int x=get(u,i);
    if(cnt[q[x].u^q[x].v^u]==2)return 0;
    return 1;
}
void del(int u){
    int x=get(u);
    to[u]=q[x].u^q[x].v^u;
    cnt[to[u]]++;
}
int main(){
    //freopen("data.in","r",stdin);
    // freopen("number.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>m;
        for(int i=1;i<=n;i++)du[i]=cnt[i]=vs[i]=0,pos[i].clear();
        for(int i=1;i<=m;i++){
            int u,v;cin>>u>>v;
            du[u]++,du[v]++;
            pos[u].pb(i),pos[v].pb(i);
            q[i]={u,v};
        }
        for(int i=1;i<=m;i++){
            int u=q[i].u,v=q[i].v;
            if(du[u]==1)cnt[v]++,to[u]=v;
            if(du[v]==1)cnt[u]++,to[v]=u;
        }
        for(int i=1;i<=m;i++){
            int u=q[i].u,v=q[i].v;
            if(check(u,i)&&check(v,i)){
                vs[i]=1,du[u]--,du[v]--;
                if(du[u]==1)del(u);
                if(du[v]==1)del(v);
            }
            // else{
            //     cout<<u<<" "<<v<<"\n";
            // }
        }
        v1.clear(),v2.clear(),v3.clear(),vec.clear(),st.clear();
        for(int i=1;i<=n;i++){
            if(cnt[i]==2){
                v3.pb(i);
            }
            else if(cnt[i]==0&&du[i]>1){
                assert(du[i]==2);
                //cout<<"find:"<<i<<"\n";
                int j=get(i),k=get(i,j),u=q[j].u^q[j].v^i,v=q[k].u^q[k].v^i;
                vec.pb({u,v,i});
            }
            else{
                assert(cnt[i]==1);
                assert(du[i]==1);
            }
        }
        for(int i=1;i<=(v3.size()+1)/2;i++)st.pb(0);
        for(int i=1;i<=v3.size()/2;i++)st.pb(1);
        // for(auto e:vec){
        //     cout<<e.u<<" "<<e.v<<" "<<e.i<<"\n";
        // }
        //for(auto e:v3)cout<<e<<" ";cout<<"\n";
        //cout<<st.size()<<"\n";
        while(1){
            shuffle(st.begin(),st.end(),gen);
            for(int i=0;i<st.size();i++)vs0[v3[i]]=st[i];
            int cnt1=0,cnt2=0;
            for(auto e:vec){
                if(vs0[e.u]!=vs0[e.v])cnt1++;
                else cnt2++;
            }
            if(cnt1>=cnt2){
                for(auto e:v3){
                    if(!vs0[e])v1.pb(e);
                    else v2.pb(e);
                }
                for(int i=1;i<=n;i++){
                    if(cnt[i]==0&&du[i]==1){
                        if(vs0[to[i]])v1.pb(i);
                        else v2.pb(i);
                    }
                }
                for(auto e:vec){
                    if(vs0[e.u]==vs0[e.v]){
                        if(vs0[e.u])v1.pb(e.i);
                        else v2.pb(e.i);
                    }
                }
                for(auto e:vec){
                    if(vs0[e.u]!=vs0[e.v]){
                        if(v1.size()<v2.size())v1.pb(e.i);
                        else v2.pb(e.i);
                    }
                }
                break;
            }
        }
        for(int i=1;i<=n;i++){
            if(cnt[i]==1){
                if(i<to[i])v1.pb(i);
                else v2.pb(i);
            }
        }
        for(auto e:v1)cout<<e<<" ";
        cout<<"\n";
    }
}