#include<iostream>
#include<vector>
#include<set>
#define nfs std::ios::sync_with_stdio(false); cin.tie(NULL);
#define pb(e) push_back(e)
#define ff first
#define ss second
#define f front()
#define pii pair<int,int>
#define mk(s,e) make_pair(min(s,e),max(s,e))
#define vii vector<pii>
#define sii set<pii>
#define i(s) insert(s)
using namespace std;
typedef long long int ll;
const ll mod_wala=1e9+7;
const int max_size=2e5+1;
vector<vector<int>> g;
vector<bool> visited;
sii pairs_path;
sii pairs;
int timer=0;
int tin[max_size]{0},low[max_size]{0};
int count=1;
void dfs(int here,int par){
	visited[here]=true;
	count++;
	tin[here]=low[here]=timer++;
	for(int child:g[here]){
		if(child==par)continue;
		if(visited[child]==true){
			low[here]=min(low[here],tin[child]);
		}else{
			dfs(child,here);
			pairs_path.insert(mk(here,child));
			low[here]=min(low[here],low[child]);
			if(low[child]>tin[here]){
				if(child==1 || here==1){
					pairs.insert(mk(child,here));
				}
			}
		}
	}
}
int main(){
	nfs;
	int n,m,d,x,y;
	cin>>n>>m>>d;
	g=vector<vector<int>>(n+1);
	visited=vector<bool>(n+1,false);
	while(m--)cin>>x>>y, g[x].pb(y), g[y].pb(x);
	dfs(1,0);
	pairs_path.clear();
	visited.clear();
	visited=vector<bool>(n+1,false);
	visited[1]=true;
	int max_d=g[1].size();
	int min_d=pairs.size();
	count=1;
	if((d<=max_d && d>min_d) || ((max_d==d) && (min_d==d))){
		int diff=d-min_d;
		for(pii child:pairs){
			if(visited[child.second]!=true){
				// cout<<"a";
				pairs_path.i(mk(1,child.second));
				dfs(child.second,1);
			}
		}
		// cout<<"b";
		if(count==n && diff>0){
			cout<<"NO\n";
		}else if(count==n && diff==0){
			cout<<"YES\n";
			for(pii here:pairs_path){
				cout<<here.ff<<" "<<here.ss<<"\n";
			}
		}else if(diff>0 && count<n){
			int diffhere=diff;
			pairs.clear();
			vector<int> kids;
			for(int child:g[1]){
				if(visited[child]!=true && diffhere>0){
					diffhere--;
					pairs_path.i(mk(1,child));
					visited[child]=true;
					kids.pb(child);
				}
			}
			for(int child:kids){
				dfs(child,1);
			}
			if(count==n){
				cout<<"YES\n";
				for(pii here:pairs_path){
					cout<<here.ff<<" "<<here.ss<<"\n";
				}
			}else{
				cout<<"NO\n";
			}
		}
	}else{
		cout<<"NO\n";
	}
	return 0;
}