#include<bits/stdc++.h>
using namespace std ;
#define F first
#define S second
const int N = 3e5+5 ;
int n , m , k , par[N] ;
vector<pair<int,int>> ans ;
int p(int k){
if(par[k]<0) return k ;
else return par[k]=p(par[k]) ;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) ;
memset(par,-1,sizeof(par)) ;
cin >> n >> m >> k ;
for(int i=0 ; i<m ; i++){
int a , b ; cin >> a >> b ;
int pa = p(a) , pb = p(b) ;
if(pa==pb){
cout << "NO\n" ; return 0 ;
}
ans.push_back({a,b}) ;
par[a]+=par[b] ; par[b]=a ;
}
// k = 0
int root = -1 ;
for(int i=0 ; i<n ; i++){
if(par[i]>=0) continue ;
if(root==-1){
root=i ; continue ;
}
par[root]+=par[i] ; par[i]=root ;
ans.push_back({i,root}) ;
}
if(ans.size()!=n-1){
cout << "NO\n" ; return 0 ;
}
for(int i=0 ; i<ans.size() ; i++) cout << ans[i].F << ' ' << ans[i].S << '\n' ;
return 0 ;
}
