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 <bits/stdc++.h>

using namespace std;

vector<int> s[30000];
vector<int> d[30000];
bool history[30000];

void connect_to_1(int n)
{
    if (!history[n])
    {
        printf("+ 1 %d\n", n+1);
        s[0].push_back(n);
        s[n].push_back(0);
    }
    history[n] = true;
    for (auto e : s[n])
    {
        if (!history[e])
            connect_to_1(e);
    }
}

void unconnect_from_1(int n)
{
    if (find(d[n].begin(), d[n].end(), 0) == d[n].end())
    {
        printf("- 1 %d\n", n+1);
    }
    history[n] = true;
    for (auto e : s[n])
    {
        if (!history[e])
            unconnect_from_1(e);
    }
}

int main()
{
    int n, m;
    scanf("%d", &n);
    scanf("%d", &m);
    int a, b;
    for (int i=0; i<m; i++)
    {
        scanf("%d %d", &a, &b);
        s[a-1].push_back(b-1);
        s[b-1].push_back(a-1);
    }
    scanf("%d", &m);
    for (int i=0; i<m; i++)
    {
        scanf("%d %d", &a, &b);
        d[a-1].push_back(b-1);
        d[b-1].push_back(a-1);
    }

    // Connect everything to 1
    for (int i=0; i<n; i++)
        history[i] = false;
    for (auto e : s[0])
        history[e] = true;
    history[0] = true;
    for (auto e : s[0])
        connect_to_1(e);

    // Make connections from d in s
    for (int i=0; i<n; i++)
    {
        vector<int> v1 = s[i];
        vector<int> v2 = d[i];
        for (auto e : v2)
        {
            if (find(v1.begin(), v1.end(), e) == v1.end())
            {
                printf("+ %d %d\n", i+1, e+1);
                s[i].push_back(e);
                s[e].push_back(i);
            }
        }
    }

    // Delete wrong connections
    // Elements are not really removed
    for (int i=1; i<n; i++)
    {
        vector<int> v1 = s[i];
        vector<int> v2 = d[i];
        for (auto e : v1)
        {
            if (i>=e || e==0) continue;
            if (find(v2.begin(), v2.end(), e) == v2.end())
            {
                printf("- %d %d\n", i+1, e+1);
            }
        }
    }

    // Delete connections with 1
    for (int i=0; i<n; i++)
        history[i] = false;
    history[0] = true;
    unconnect_from_1(d[0][0]);

    return 0;
}