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
108
109
110
#include <bits/stdc++.h>

using namespace std;



void dfs(int vertice, vector<set<int>> &current_molecule, vector<int> &visited, vector<int> &order)
{
    order.push_back(vertice);
    visited[vertice] = 1;
    for(auto i: current_molecule[vertice])
    {
        if(!visited[i])
        {
            dfs(i, current_molecule, visited, order);
        }
    }
}

void dfs_2(int vertice, vector<set<int>> &wanted_molecule, vector<int> &visited, vector<int> &order)
{
    visited[vertice] = 1;
    for(auto i: wanted_molecule[vertice])
    {
        if(!visited[i])
        {
            dfs(i, wanted_molecule, visited, order);
        }
    }
    order.push_back(vertice);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<set<int>> current_molecule(n);
    vector<int> visited(n);
    vector<int> order;
    int x,y;
    for(int i = 0; i <m; i++)
    {
        cin >> x >> y;
        current_molecule[x - 1].insert(y - 1);
        current_molecule[y - 1].insert(x - 1);
    }
    vector<string> answers;
    dfs(0, current_molecule, visited, order);
    int r = 0;
    for(int i = 0; i < order.size(); i++)
    {
        if(current_molecule[0].find(order[i]) == current_molecule[0].end() && order[i] != 0)
        {
            r++;
            answers.push_back("+ 1 " + to_string(order[i] + 1));
            current_molecule[0].insert(order[i]);
            current_molecule[order[i]].insert(0);
        }
    }
    cin >> m;
    vector<set<int>> wanted_molecule(n);
    for(int i = 0; i < m; i++)
    {
        cin >> x >> y;
        wanted_molecule[x - 1].insert(y - 1);
        wanted_molecule[y - 1].insert(x - 1);
    }
    for(int i = 0; i < n; i++)
    {
        for(auto k: wanted_molecule[i])
        {
            if(current_molecule[i].find(k) == current_molecule[i].end())
            {
                r++;
                answers.push_back("+ " + to_string(i + 1) + " " + to_string(k + 1));
                current_molecule[k].insert(i);
            }
        }
    }
    for(int i = 1; i < n; i++)
    {
        for(auto k: current_molecule[i])
        {
            if(wanted_molecule[i].find(k) == wanted_molecule[i].end() && k != 0)
            {
                r++;
                answers.push_back("- " + to_string(i + 1) + " " + to_string(k + 1));
                current_molecule[k].erase(i);
            }
        }
    }
    order.clear();
    fill(visited.begin(), visited.end(), 0);
    dfs_2(0, wanted_molecule,visited, order);
    for(int i = 0; i < order.size(); i++)
    {
        if(wanted_molecule[order[i]].find(0) == wanted_molecule[order[i]].end() && order[i] != 0)
        {
            r++;
            answers.push_back("- 1 " + to_string(order[i] + 1));
        }
    }
    cout << r << "\n";
    for(int i = 0; i < r; i++)
    {
        cout << answers[i] << "\n";
    }
}