102962024-03-30 10:48:41111Pletykálkodáscpp17Futási hiba 0/10059ms8120 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,M;
	cin>>N>>M;
	vector<vector<int>>g(N+1);
	for(int i=0;i<M;i++){
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	vector<tuple<int,int,int,int>>c;
	for(int i=1;i<=N;i++){
		vector<int>v(N+1);
		v[i]=-1;
		for(int j:g[i]){
			v[j]=-1;
		}
		for(int j:g[i]){
			for(int k:g[j]){
				if(v[k]<0){
					continue;
				}
				if(v[k]>0){
					c.emplace_back(i,j,v[k],k);
					continue;
				}
				v[k]=j;
			}
		}
	}
	for(auto[a,b,aa,bb]:c){
		vector<int>v(N+1,-1);
		vector<vector<pair<int,int>>>w(2);
		auto dfs=[&](auto self,int i)->void{
			for(int j:g[i]){
				if(v[j]!=-1){
					continue;
				}
				v[j]=v[i];
				self(self,j);
				w[v[i]].emplace_back(i,j);
			}
		};
		v[a]=0;
		v[b]=1;
		v[aa]=0;
		v[bb]=1;
		dfs(dfs,aa);
		dfs(dfs,bb);
		if(count(v.begin(),v.end(),-1)==1){
			vector<pair<int,int>>s;
			for(auto[a,b]:w[0]){
				s.emplace_back(a,b);
			}
			for(auto[a,b]:w[1]){
				s.emplace_back(a,b);
			}
			s.emplace_back(a,aa);
			s.emplace_back(b,bb);
			s.emplace_back(a,b);
			s.emplace_back(aa,bb);
			reverse(w[0].begin(),w[0].end());
			reverse(w[1].begin(),w[1].end());
			for(auto[a,b]:w[0]){
				s.emplace_back(a,b);
			}
			for(auto[a,b]:w[1]){
				s.emplace_back(a,b);
			}
			cout<<s.size()<<'\n';
			for(auto[a,b]:s){
				cout<<a<<' '<<b<<'\n';
			}
			return 0;
		}
	}
	return 1;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Futási hiba3ms1828 KiB
2Futási hiba3ms2016 KiB
3Elfogadva4ms2668 KiB
subtask20/9
4Futási hiba3ms2444 KiB
5Futási hiba3ms2532 KiB
6Elfogadva3ms2528 KiB
subtask30/13
7Futási hiba16ms3508 KiB
8Futási hiba20ms3704 KiB
9Futási hiba19ms3776 KiB
subtask40/16
10Futási hiba14ms3696 KiB
11Futási hiba14ms3952 KiB
12Futási hiba14ms4272 KiB
subtask50/25
13Elfogadva3ms3580 KiB
14Elfogadva3ms3708 KiB
15Elfogadva3ms3836 KiB
16Futási hiba3ms3780 KiB
17Futási hiba3ms3872 KiB
18Futási hiba3ms3780 KiB
19Elfogadva3ms3876 KiB
subtask60/13
20Elfogadva4ms4556 KiB
21Elfogadva8ms4600 KiB
22Elfogadva4ms4824 KiB
23Futási hiba8ms4844 KiB
24Futási hiba6ms4720 KiB
25Futási hiba4ms4760 KiB
26Elfogadva6ms5084 KiB
subtask70/24
27Elfogadva27ms7776 KiB
28Elfogadva35ms8120 KiB
29Elfogadva27ms8032 KiB
30Futási hiba35ms6308 KiB
31Futási hiba39ms6124 KiB
32Futási hiba43ms5944 KiB
33Futási hiba52ms5892 KiB
34Futási hiba59ms5844 KiB
35Elfogadva41ms7204 KiB
36Elfogadva46ms6884 KiB
37Elfogadva54ms6812 KiB