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;

void dfs(int v, vector<vector<int>> &G, vector<bool> &visited, vector<vector<bool>> &arr, vector<tuple<bool,int,int>> &ans) {
    visited[v] = 1;
    for(auto u: G[v]) {
        if(!visited[u]) {
            if(arr[0][u] == 0) {
                ans.push_back({1,0,u});
                arr[0][u] = 1;
                arr[u][0] = 1;
            }
            dfs(u, G, visited, arr, ans);
        }
    }
}

void dfs2(int v, vector<vector<int>> &G, vector<bool> &visited, vector<vector<bool>> &arr, vector<tuple<bool,int,int>> &ans) {
    visited[v] = 1;
    for(auto u: G[v]) {
        if(!visited[u]) {
            dfs2(u, G, visited, arr, ans);
        }
    }
    if(arr[0][v] == 0 && v != 0) {
        ans.push_back({0,0,v});
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,m; cin>>n>>m;
    vector<vector<bool>> arr(n, vector<bool>(n));
    vector<vector<int>> G(n), G2(n);
    vector<tuple<bool,int,int>> ans;
    int a,b;
    for(int i=0; i<m; i++) {
        cin>>a>>b;
        a--; b--;
        arr[a][b]=1;
        arr[b][a]=1;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    // łączymy wierzchołek 0 ze wszystkimi

    vector<bool> visited(n);
    dfs(0, G, visited, arr, ans);

    vector<vector<bool>> final(n, vector<bool>(n));
    cin>>m;
    int stay = -1;
    for(int i=0; i<m; ++i) {
        cin>>a>>b;
        a--; b--;
        if(a == 0 && stay == -1) stay = b;
        if(b == 0 && stay == -1) stay = a;
        final[a][b] = 1;
        final[b][a] = 1;
        G2[a].push_back(b);
        G2[b].push_back(a);
    }

    for(int i=1; i<n; ++i) {
        for(int j=i+1; j<n; ++j) {
            if(arr[i][j] != final[i][j]) {
                if(final[i][j] == 1) {
                    ans.push_back({1,i,j});
                } else {
                    ans.push_back({0,i,j});
                }
            }
        }
    }

    // usuwanie krawedzi od wierzcholka 0 poza stay

    vector<bool> visited2(n);
    dfs2(0, G2, visited2, final, ans);

    cout<<ans.size()<<'\n';
    for(auto [a,b,c]: ans) {
        if(a) {
            cout<<"+ "<<b+1<<' '<<c+1<<'\n';
        } else {
            cout<<"- "<<b+1<<' '<<c+1<<'\n';
        }
    }
    
    return 0;
}