#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second

using namespace std;
const int N=5e4;
int T;
int n,m,k;
vector<int>g[N+10];
int val[N+10][2],in[N+10];
set<pii >s[2];
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m>>k;
		for(int i=1;i<=n;++i){
			g[i].clear();
			val[i][0]=0;
			val[i][1]=0;
			in[i]=-1;
		}
		for(int i=1;i<=m;++i){
			int u,v;
			cin>>u>>v;
			g[u].push_back(v);
			g[v].push_back(u);
		}
		vector<int>p[2];
		for(int i=1;i<=n;++i){
			if(val[i][0]>=val[i][1]){
				in[i]=1;
				p[1].push_back(i);
				for(auto j:g[i]){
					++val[j][1];
				}
			}
			else{
				in[i]=0;
				p[0].push_back(i);
				for(auto j:g[i]){
					++val[j][0];
				}
			}
		}
		s[0].clear();
		s[1].clear();
		for(auto x:p[0]){
			s[0].insert({val[x][1],x});
		}
		for(auto x:p[1]){
			s[1].insert({val[x][0],x});
		}
		while((*s[0].begin()).fi<=k||(*s[1].begin()).fi<=k){
			if((*s[0].begin()).fi<=k){
				pii tmp=(*s[0].begin());
				s[0].erase(s[0].begin());
				in[tmp.se]=-1;
				for(auto v:g[tmp.se]){
					if(in[v]==1){
						s[1].erase(s[1].find({val[v][0],v}));
						--val[v][0];
						s[1].insert({val[v][0],v});
					}
				}
			}
			else{
				pii tmp=(*s[1].begin());
				s[1].erase(s[1].begin());
				in[tmp.se]=-1;
				for(auto v:g[tmp.se]){
					if(in[v]==0){
						s[0].erase(s[0].find({val[v][1],v}));
						--val[v][1];
						s[0].insert({val[v][1],v});
					}
				}
			}
		}
		cout<<(int)s[0].size()<<' ';
		for(auto x:s[0]){
			cout<<x.se<<' ';
		}
		cout<<'\n';
		cout<<(int)s[1].size()<<' ';
		for(auto x:s[1]){
			cout<<x.se<<' ';
		}
		cout<<'\n';
	}
	return 0;
}