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
#include<bits/stdc++.h>
using namespace std;
vector<char>typ;
vector<int>w1,w2;
vector<bool>odw(31000,0);
vector<set<int>> gr1(31000,set<int>());
vector<set<int>> gr2(31000,set<int>());
void Dfs1(int w){
    odw[w]=1;
    if(gr1[1].find(w)==gr1[1].end()&&w!=1){
        gr1[1].insert(w);
        gr1[w].insert(1);
        typ.push_back('+');
        w1.push_back(1);
        w2.push_back(w);
    }
    for(auto syn:gr1[w]){
        if(odw[syn])
            continue;
        Dfs1(syn);
    }
}
void Dfs2(int w){
    odw[w]=1;
    for(auto syn:gr2[w]){
        if(odw[syn]){
            continue;
        }
        Dfs2(syn);
    }
    if(gr2[w].find(1)==gr2[w].end()&&w!=1){
        gr1[w].erase(1);
        typ.push_back('-');
        w2.push_back(w);
        w1.push_back(1);
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int lw,lkr;
    cin>>lw>>lkr;
    for (int i=0; i<lkr; i++) {
        int ina,inb;
        cin>>ina>>inb;
        gr1[ina].insert(inb);
        gr1[inb].insert(ina);
    }
    int lkr2;
    cin>>lkr2;
    for (int i=0; i<lkr2; i++){
        int ina,inb; 
        cin>>ina>>inb;
        gr2[ina].insert(inb);
        gr2[inb].insert(ina);
    }
    
    Dfs1(1);
    for (int i=2; i<=lw; i++){
        vector<int>toerase;
        for(auto syn:gr1[i]){
            if(syn==1)
                continue;
            if(gr2[i].find(syn)==gr2[i].end()){
                typ.push_back('-');
                w2.push_back(syn);
                w1.push_back(i);
                gr1[syn].erase(i);
                toerase.push_back(syn);
                //gr1[i].erase(syn);
            }
        }
        for(auto x:toerase){
            gr1[i].erase(x);
        }
        for(auto syn:gr2[i]){
            if(gr1[i].find(syn)==gr1[i].end()){
                gr1[i].insert(syn);
                gr1[syn].insert(i);
                typ.push_back('+');
                w2.push_back(syn);
                w1.push_back(i);
            }
        }
    }
    odw=vector<bool>(31000);
    Dfs2(1);
    int r=typ.size();
    cout<<r<<"\n";
    for(int i=0; i<r; i++){
        cout<<typ[i]<<" "<<w1[i]<<" "<<w2[i]<<"\n";
    }

}