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
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define pb push_back
#define ssize(v) (int)(v.size())

constexpr int MAX_N=3e4+14;
struct resS{
    char val;
    int a,b;
};
int N, M1, M2;
vector<int> edg1[MAX_N], edg2[MAX_N];
bitset<MAX_N> grph1[MAX_N], grph2[MAX_N], vis;
vector<resS> rres;

void Input(){
    int a,b;
    cin>>N>>M1;
    FOR(i,0,N) grph1[i][i]=1, grph2[i][i]=1;
    FOR(i,0,M1-1){
        cin>>a>>b;
        edg1[a].pb(b), edg1[b].pb(a);
        grph1[a][b]=1, grph1[b][a]=1;
    }
    cin>>M2;
    FOR(i,0,M2-1){
        cin>>a>>b;
        edg2[a].pb(b), edg2[b].pb(a);
        grph2[a][b]=1, grph2[b][a]=1;
    }
}
void DFSAddOnes(int cV){
    vis[cV]=1;
    if(!grph1[1][cV]){
        grph1[1][cV]=1, grph1[cV][1]=1;
        edg1[1].pb(cV), edg1[cV].pb(1);
        rres.pb({'+',1,cV});
    }
    FOR(i,0,ssize(edg1[cV])-1)
        if(!vis[edg1[cV][i]]) DFSAddOnes(edg1[cV][i]);
}
void AddRest(){
    FOR(cV,1,N){
        for(auto nV:edg2[cV]){
            if(!grph1[cV][nV]){
                grph1[cV][nV]=1, grph1[nV][cV]=1;
                edg1[cV].pb(nV), edg1[nV].pb(cV);
                rres.pb({'+',cV,nV});
            }
        }
    }
}
void DelRest(){
    FOR(cV,2,N){
        for(auto nV:edg1[cV]){
            if(!grph2[cV][nV]&&grph1[cV][nV]&&nV!=1){
                grph1[cV][nV]=0, grph1[nV][cV]=0;
                rres.pb({'-',cV,nV});
            }
        }
    }
    FOR(i,0,N) vis[i]=0;
}
void DFSDelOnes(int cV){
    vis[cV]=1;
    for(auto nV:edg2[cV]){
        if(!vis[nV]) DFSDelOnes(nV);
    }
    if(!grph2[1][cV]&&grph1[1][cV]){
        grph1[1][cV]=0, grph1[cV][1]=0;
        rres.pb({'-',1,cV});
    }
}
void Print(){
    cout<<ssize(rres)<<"\n";
    for(auto cE:rres) cout<<cE.val<<" "<<cE.a<<" "<<cE.b<<"\n";
    
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    Input();
    DFSAddOnes(1);
    AddRest();
    DelRest();
    DFSDelOnes(1);
    Print();
}