#include<bits/stdc++.h> using namespace std; set<pair<int,int>> v1; set<pair<int,int>> v2; vector<int> pol1[1000005]; vector<int> pol2[1000005]; bool good1[1000005]; bool good2[1000005]; bool odw1[1000005]; bool odw2[1000005]; vector<pair<char, pair<int,int>>> out; vector<pair<char, pair<int,int>>> out2; void dfs1(int a) { odw1[a] = true; if(!good1[a] && a != 1) { good1[a] = true; v1.insert({1, a}); out.push_back({'+', {1, a}}); } for(auto x : pol1[a]) if(!odw1[x]) dfs1(x); } void dfs2(int a) { odw2[a] = true; if(!good2[a] && a != 1) { good2[a] = true; v2.insert({1, a}); out2.push_back({'+', {1, a}}); } for(auto x : pol2[a]) if(!odw2[x]) dfs2(x); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int a; cin>>a; int b; cin>>b; while(b--) { int c, d; cin>>c>>d; if(c > d) swap(c, d); pol1[c].push_back(d); pol1[d].push_back(c); v1.insert({c, d}); if(c == 1) good1[d] = true; } cin>>b; while(b--) { int c, d; cin>>c>>d; if(c > d) swap(c, d); pol2[c].push_back(d); pol2[d].push_back(c); v2.insert({c, d}); if(c == 1) good2[d] = true; } dfs1(1); for(auto p : v2) { auto it = v1.find(p); if(it == v1.end()) { v1.insert(p); out.push_back({'+', p}); } } dfs2(1); for(auto p : v1) { auto it = v2.find(p); if(it == v2.end()) { v2.insert(p); out2.push_back({'+', p}); } } reverse(out2.begin(), out2.end()); for(auto p : out2) out.push_back({'-', p.second}); cout<<out.size()<<'\n'; for(auto p : out) cout<<p.first<<" "<<p.second.first<<" "<<p.second.second<<'\n'; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 | #include<bits/stdc++.h> using namespace std; set<pair<int,int>> v1; set<pair<int,int>> v2; vector<int> pol1[1000005]; vector<int> pol2[1000005]; bool good1[1000005]; bool good2[1000005]; bool odw1[1000005]; bool odw2[1000005]; vector<pair<char, pair<int,int>>> out; vector<pair<char, pair<int,int>>> out2; void dfs1(int a) { odw1[a] = true; if(!good1[a] && a != 1) { good1[a] = true; v1.insert({1, a}); out.push_back({'+', {1, a}}); } for(auto x : pol1[a]) if(!odw1[x]) dfs1(x); } void dfs2(int a) { odw2[a] = true; if(!good2[a] && a != 1) { good2[a] = true; v2.insert({1, a}); out2.push_back({'+', {1, a}}); } for(auto x : pol2[a]) if(!odw2[x]) dfs2(x); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int a; cin>>a; int b; cin>>b; while(b--) { int c, d; cin>>c>>d; if(c > d) swap(c, d); pol1[c].push_back(d); pol1[d].push_back(c); v1.insert({c, d}); if(c == 1) good1[d] = true; } cin>>b; while(b--) { int c, d; cin>>c>>d; if(c > d) swap(c, d); pol2[c].push_back(d); pol2[d].push_back(c); v2.insert({c, d}); if(c == 1) good2[d] = true; } dfs1(1); for(auto p : v2) { auto it = v1.find(p); if(it == v1.end()) { v1.insert(p); out.push_back({'+', p}); } } dfs2(1); for(auto p : v1) { auto it = v2.find(p); if(it == v2.end()) { v2.insert(p); out2.push_back({'+', p}); } } reverse(out2.begin(), out2.end()); for(auto p : out2) out.push_back({'-', p.second}); cout<<out.size()<<'\n'; for(auto p : out) cout<<p.first<<" "<<p.second.first<<" "<<p.second.second<<'\n'; return 0; } |