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
105
106
107
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
using namespace std;
vector<vector<int>>tabs,tabd;
vector<bool>visited;
vector<int>parent;

vector<int> bfs(int x,int y,int n,vector<vector<int>>tab){
    queue<int>q;
    visited.clear();visited.resize(n+1,false);
    parent.clear();parent.resize(n+1,0);
    q.push(x);
    visited[x]=true;
    bool found=false;
    while(!q.empty() && !found){
        int a = q.front();
        q.pop();    
        for(int i = 0;i<tab[a].size();++i){
            int b = tab[a][i];
            if(!visited[b]){
                parent[b]=a;
                visited[b]=true;
                q.push(b);
                if(b==y){
                    found=true;
                    break;
                }
            }
        }
    }
    vector<int>res;
    int c = y;
    while(c!=x){
        res.push_back(c);
        c=parent[c];
    }
    res.push_back(x);
    return res;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,ms,md;
    cin>>n;
    tabs.resize(n+1);
    tabd.resize(n+1);
    cin>>ms;
    int a,b;
    for(int i = 0;i<ms;++i){
        cin>>a>>b;
        tabs[a].push_back(b);
        tabs[b].push_back(a);
    }
    cin>>md;
    for(int i = 0;i<md;++i){
        cin>>a>>b;
        tabd[a].push_back(b);
        tabd[b].push_back(a);
    }
    int ile = 0;
    vector<string>wynik;
    for(int i = 1;i<=n;++i){
        for(int j = 0;j<tabd[i].size();++j){
            if(find(tabs[i].begin(),tabs[i].end(),tabd[i][j])==tabs[i].end()){
                vector<int>path=bfs(i,tabd[i][j],n,tabs);
                for(int a = 2;a<path.size();++a){
                    ++ile;
                    wynik.push_back("+ "+to_string(path[0])+" "+to_string(path[a])+"\n");
                    tabs[path[0]].push_back(path[a]);
                    tabs[path[a]].push_back(path[0]);
                }
            }
        }
    }
    for(int i = 1;i<=n;++i){
        for(int j = 0;j<tabs[i].size();++j){
            if(find(tabd[i].begin(),tabd[i].end(),tabs[i][j])==tabd[i].end()){
                int tgt=tabs[i][j];
                tabs[i].erase(tabs[i].begin()+j);
                tabs[tgt].erase(find(tabs[tgt].begin(),tabs[tgt].end(),i));
                vector<int>path=bfs(i,tgt,n,tabs);
                
                for(int a = 2;a<path.size()-1;++a){
                    ++ile;
                    wynik.push_back("+ "+to_string(path[0])+" "+to_string(path[a])+"\n");
                }
                ++ile;
                wynik.push_back("- "+to_string(i)+" "+to_string(tgt)+"\n");
                for(int a = path.size()-2;a>1;--a){
                    ++ile;
                    wynik.push_back("- "+to_string(path[0])+" "+to_string(path[a])+"\n");
                }
            }
        }
    }
    cout<<ile<<"\n";
    for(string s : wynik){
        cout<<s;
    }
    return 0;

}