提出 #71367625

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define cmin(a,b) a=std::min(a,b)
#define cmax(a,b) a=std::max(a,b)
#define inf
#define mod
#define maxn 300005
#define int long long
int n,m,to1[maxn],to2[maxn];
std::vector<int> to[maxn];
std::map<int,int> mp[maxn];
std::queue<int> que;
int vis1[maxn],vis2[maxn];
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1,u,v;i<=m;i++){
		scanf("%lld%lld",&u,&v);
		to[u].push_back(v);
		to[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		std::sort(to[i].begin(),to[i].end());
	}
	que.push(1),vis1[1]=1;
	while(!que.empty()){
		int x=que.front();que.pop();
		for(int v:to[x]){
			if(vis1[v]) continue;
			vis1[v]=1,to1[v]=x,que.push(v);
			mp[x][v]=1;
		}
	}
	for(int i=1;i<=n;i++){
		std::sort(to[i].begin(),to[i].end(),std::greater<int>());
	}
	que.push(2),vis2[2]=1;
	int cnt=0;
	while(!que.empty()){
		int x=que.front();que.pop();cnt++;
		for(int v:to[x]){
			if(vis2[v]||mp[x][v]) continue;
			vis2[v]=1,to2[v]=x,que.push(v);
		}
	}
	if(cnt!=n){
		puts("No");
	}else{
		puts("Yes");
		printf("%lld\n%lld\n",to2[1],to1[2]);
		for(int i=3;i<=n;i++){
			printf("%lld %lld\n",to1[i],to2[i]); 
		}
	}
	return 0;
}
/*

*/

提出情報

ジャッジ結果