fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<set>
  4. #define nfs std::ios::sync_with_stdio(false); cin.tie(NULL);
  5. #define pb(e) push_back(e)
  6. #define ff first
  7. #define ss second
  8. #define f front()
  9. #define pii pair<int,int>
  10. #define mk(s,e) make_pair(min(s,e),max(s,e))
  11. #define vii vector<pii>
  12. #define sii set<pii>
  13. #define i(s) insert(s)
  14. using namespace std;
  15. typedef long long int ll;
  16. const ll mod_wala=1e9+7;
  17. const int max_size=2e5+1;
  18. vector<vector<int>> g;
  19. vector<bool> visited;
  20. sii pairs_path;
  21. sii pairs;
  22. int timer=0;
  23. int tin[max_size]{0},low[max_size]{0};
  24. int count=1;
  25. void dfs(int here,int par){
  26. 	visited[here]=true;
  27. 	count++;
  28. 	tin[here]=low[here]=timer++;
  29. 	for(int child:g[here]){
  30. 		if(child==par)continue;
  31. 		if(visited[child]==true){
  32. 			low[here]=min(low[here],tin[child]);
  33. 		}else{
  34. 			dfs(child,here);
  35. 			pairs_path.insert(mk(here,child));
  36. 			low[here]=min(low[here],low[child]);
  37. 			if(low[child]>tin[here]){
  38. 				if(child==1 || here==1){
  39. 					pairs.insert(mk(child,here));
  40. 				}
  41. 			}
  42. 		}
  43. 	}
  44. }
  45. int main(){
  46. 	nfs;
  47. 	int n,m,d,x,y;
  48. 	cin>>n>>m>>d;
  49. 	g=vector<vector<int>>(n+1);
  50. 	visited=vector<bool>(n+1,false);
  51. 	while(m--)cin>>x>>y, g[x].pb(y), g[y].pb(x);
  52. 	dfs(1,0);
  53. 	pairs_path.clear();
  54. 	visited.clear();
  55. 	visited=vector<bool>(n+1,false);
  56. 	visited[1]=true;
  57. 	int max_d=g[1].size();
  58. 	int min_d=pairs.size();
  59. 	count=1;
  60. 	if((d<=max_d && d>min_d) || ((max_d==d) && (min_d==d))){
  61. 		int diff=d-min_d;
  62. 		for(pii child:pairs){
  63. 			if(visited[child.second]!=true){
  64. 				// cout<<"a";
  65. 				pairs_path.i(mk(1,child.second));
  66. 				dfs(child.second,1);
  67. 			}
  68. 		}
  69. 		// cout<<"b";
  70. 		if(count==n && diff>0){
  71. 			cout<<"NO\n";
  72. 		}else if(count==n && diff==0){
  73. 			cout<<"YES\n";
  74. 			for(pii here:pairs_path){
  75. 				cout<<here.ff<<" "<<here.ss<<"\n";
  76. 			}
  77. 		}else if(diff>0 && count<n){
  78. 			int diffhere=diff;
  79. 			pairs.clear();
  80. 			vector<int> kids;
  81. 			for(int child:g[1]){
  82. 				if(visited[child]!=true && diffhere>0){
  83. 					diffhere--;
  84. 					pairs_path.i(mk(1,child));
  85. 					visited[child]=true;
  86. 					kids.pb(child);
  87. 				}
  88. 			}
  89. 			for(int child:kids){
  90. 				dfs(child,1);
  91. 			}
  92. 			if(count==n){
  93. 				cout<<"YES\n";
  94. 				for(pii here:pairs_path){
  95. 					cout<<here.ff<<" "<<here.ss<<"\n";
  96. 				}
  97. 			}else{
  98. 				cout<<"NO\n";
  99. 			}
  100. 		}
  101. 	}else{
  102. 		cout<<"NO\n";
  103. 	}
  104. 	return 0;
  105. }
Runtime error #stdin #stdout 0s 4368KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/t7TNO6
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!