#include<bits/stdc++.h> #define poly vector<int> #define IOS ios::sync_with_stdio(false) #define ll long long #define mp make_pair #define mt make_tuple #define pa pair < int,int > #define fi first #define se second #define inf 1e18 #define mod 998244353 #define sz(x) (int)((x).size()) #define int ll //#define N using namespace std; const int N=200005; poly G[N],G1[N]; map<pa,int>Mp,F; int n,m; int vis[N]; vector<pair<pa,int>>ans; void dfs(int k,int fa) { vis[k]=1; if (k!=1&&!Mp.count(mp(1,k))) { ans.push_back(mp(mp(1,k),1)); Mp[mp(1,k)]++; } for (auto u:G[k]) { if (vis[u]) continue; dfs(u,k); } } void dfs1(int k,int fa) { vis[k]=1; for (auto u:G1[k]) { if (vis[u]) continue; dfs1(u,k); } if (k!=1&&fa!=1&&!F.count(mp(1,k))) { ans.push_back(mp(mp(1,k),2)); } } void BellaKira() { cin>>n; cin>>m; int tot=m; for (int i=1;i<=m;i++) { int x,y; cin>>x>>y; if (x>y)swap(x,y); Mp[mp(x,y)]++; G[x].push_back(y); G[y].push_back(x); } dfs(1,0); cin>>m; for (int i=1;i<=m;i++) { int x,y; cin>>x>>y; if (x>y) swap(x,y); F[mp(x,y)]++; G1[x].push_back(y); G1[y].push_back(x); if (!Mp.count(mp(x,y))) { ans.push_back(mp(mp(x,y),1)); Mp[mp(x,y)]++; } } for (auto [u,v]:Mp) if (!F.count(u)) { auto [x,y]=u; // assert(x<y); if (x==1) continue; ans.push_back(mp(mp(x,y),2)); } for (int i=1;i<=n;i++) vis[i]=0; dfs1(1,0); cout<<sz(ans)<<'\n'; for (auto u:ans) if (u.se==1) cout<<"+ "<<u.fi.fi<<" "<<u.fi.se<<'\n',tot++; else cout<<"- "<<u.fi.fi<<" "<<u.fi.se<<'\n',tot--; // cout<<tot<<" "<<m<<" "<<sz(Mp)<<endl; } signed main() { IOS; cin.tie(0); int T=1; while (T--) { BellaKira(); } }
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 100 101 102 103 104 | #include<bits/stdc++.h> #define poly vector<int> #define IOS ios::sync_with_stdio(false) #define ll long long #define mp make_pair #define mt make_tuple #define pa pair < int,int > #define fi first #define se second #define inf 1e18 #define mod 998244353 #define sz(x) (int)((x).size()) #define int ll //#define N using namespace std; const int N=200005; poly G[N],G1[N]; map<pa,int>Mp,F; int n,m; int vis[N]; vector<pair<pa,int>>ans; void dfs(int k,int fa) { vis[k]=1; if (k!=1&&!Mp.count(mp(1,k))) { ans.push_back(mp(mp(1,k),1)); Mp[mp(1,k)]++; } for (auto u:G[k]) { if (vis[u]) continue; dfs(u,k); } } void dfs1(int k,int fa) { vis[k]=1; for (auto u:G1[k]) { if (vis[u]) continue; dfs1(u,k); } if (k!=1&&fa!=1&&!F.count(mp(1,k))) { ans.push_back(mp(mp(1,k),2)); } } void BellaKira() { cin>>n; cin>>m; int tot=m; for (int i=1;i<=m;i++) { int x,y; cin>>x>>y; if (x>y)swap(x,y); Mp[mp(x,y)]++; G[x].push_back(y); G[y].push_back(x); } dfs(1,0); cin>>m; for (int i=1;i<=m;i++) { int x,y; cin>>x>>y; if (x>y) swap(x,y); F[mp(x,y)]++; G1[x].push_back(y); G1[y].push_back(x); if (!Mp.count(mp(x,y))) { ans.push_back(mp(mp(x,y),1)); Mp[mp(x,y)]++; } } for (auto [u,v]:Mp) if (!F.count(u)) { auto [x,y]=u; // assert(x<y); if (x==1) continue; ans.push_back(mp(mp(x,y),2)); } for (int i=1;i<=n;i++) vis[i]=0; dfs1(1,0); cout<<sz(ans)<<'\n'; for (auto u:ans) if (u.se==1) cout<<"+ "<<u.fi.fi<<" "<<u.fi.se<<'\n',tot++; else cout<<"- "<<u.fi.fi<<" "<<u.fi.se<<'\n',tot--; // cout<<tot<<" "<<m<<" "<<sz(Mp)<<endl; } signed main() { IOS; cin.tie(0); int T=1; while (T--) { BellaKira(); } } |