#include<bits/stdc++.h>
using namespace std;
namespace sub1{
	#define nperm next_permutation
	const int maxn=1e5+5;
	int T,n,m,u[maxn],v[maxn];
	int p[maxn],q[maxn],a[maxn],b[maxn];
	inline int jug(int i,int j){
		return a[i]<a[j]&&a[j]<b[i]&&b[i]<b[j];
	}
	inline int chk(){
		for(int i=1;i<=n;i++)q[p[i]]=i;
		for(int i=1;i<=m;i++){
			a[i]=q[u[i]];b[i]=q[v[i]];
			if(a[i]>b[i])swap(a[i],b[i]);
		}
		for(int i=1;i<=m;i++)
		for(int j=1;j<=m;j++)
			if(jug(i,j))return 0;
		return 1;
	}
	inline void solve(){
		cin>>T;while(T--){
			cin>>n>>m;
			for(int i=1;i<=m;i++)
				cin>>u[i]>>v[i];
			for(int i=1;i<=n;i++)p[i]=i;
			do if(chk())break;
			while(nperm(p+1,p+n+1));
			for(int i=1;i<=n;i++)
				cout<<p[i]<<" \n"[i==n];
		}
	}
}
namespace sub2{
	using pii=pair<int,int>;
	#define fi first
	#define se second
	const int maxn=1e5+5;
	int T,n,m,u,v,fa[maxn];
	int c,x,p[maxn];
	vector<int>e[maxn];
	vector<pii>g[maxn];
	vector<int>a[maxn];
	int dfs(int u,int f){
		fa[u]=f;int x=u,y;
		for(int &v:e[u])if(v!=f){
			y=dfs(v,u);x=min(x,y);
			g[u].push_back({y,v});
		}
		stable_sort(g[u].begin(),g[u].end());
		return x;
	}
	void Dfs(int u,int f,int i){
		a[i].emplace_back(u);
		for(pii p:g[u])
			Dfs(p.fi,p.se,i);
		for(int v=fa[u];u!=f;){
			int h=0;
			for(pii p:g[v]){
				if(p.se==u)continue;
				if(!h&&v<p.fi)
					a[i].emplace_back(v),h=1;
				Dfs(p.fi,p.se,i);
			}
			if(!h)a[i].emplace_back(v);
			u=v;v=fa[u];
		}
	}
	struct dsu{
		int fa[maxn],sz[maxn];
		inline void init(){
			for(int i=1;i<=n;i++)
				fa[i]=i,sz[i]=1;
		}
		int find(int x){
			if(fa[x]==x)return x;
			return fa[x]=find(fa[x]);
		}
		inline void merge(int x,int y){
			x=find(x);y=find(y);
			if(x>y)swap(x,y);
			fa[y]=x;
		}
		inline int hd(int x){
			return fa[x]==x;
		}
	}A;
	inline void solve(){
		cin>>T;while(T--){
			cin>>n>>m;A.init();c=0;
			while(m--){
				cin>>u>>v;A.merge(u,v);
				e[u].emplace_back(v);
				e[v].emplace_back(u);
			}
			for(int i=1;i<=n;i++)
				if(A.hd(i))dfs(i,0);
			for(int i=1;i<=n;i++)
				if(A.hd(i))Dfs(i,i,++c);
			for(int i=1;i<=c;i++){
				x=(int)a[i].size();
				for(p[i]=0;p[i]<x;p[i]++){
					if(i<c&&a[i][p[i]]>a[i+1][0])break;
					cout<<a[i][p[i]]<<' ';
				}
				for(int j=i-1;j;j--){
					if(p[j+1]!=x)break;
					x=(int)a[j].size();
					while(p[j]<x&&(i==c||a[j][p[j]]>a[i+1][0]))
						cout<<a[j][p[j]++]<<' ';
				}
			}
			cout<<'\n';
			for(int i=1;i<=n;i++){
				e[i].clear();
				g[i].clear();
			}
			for(int i=1;i<=c;i++)
				a[i].clear();
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	freopen("graperm.in","r",stdin);
	freopen("graperm.out","w",stdout);
	int c;cin>>c;
	if(c==1||c==2)sub1::solve();
	else sub2::solve();
	return 0;
}