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
111
112
113
#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> par;
typedef pair<int, par> tr;
vector<tr> wyn;
vector<par> v1, v2;
vector<int> graf1[30009], graf2[30009], ord;
int col[30009];
queue<int> q;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, m1, m2, a, b;
    cin>>n>>m1;
    for(int i=1; i<=m1; i++)
    {
        cin>>a>>b;
        if(a > b) swap(a, b);
        if(a != 1 && b!= 1) v1.push_back(par(a, b));
        graf1[a].push_back(b);
        graf1[b].push_back(a);
    }
    cin>>m2;
    for(int i=1; i<=m2; i++)
    {
        cin>>a>>b;
        if(a > b) swap(a, b);
        if(a != 1 && b!= 1) v2.push_back(par(a, b));
        graf2[a].push_back(b);
        graf2[b].push_back(a);
    }
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    
    // prep
    col[1] = 1;
    q.push(1);
    while(!q.empty())
    {
        a = q.front();
        q.pop();
        if(col[a] > 2) wyn.push_back(tr(1, par(1, a))); // cout<<"+ 1 "<<a<<"\n";
        for(int i=0; i<graf1[a].size(); i++)
        {
            b = graf1[a][i];
            if(col[b] == 0)
            {
                col[b] = col[a] + 1;
                q.push(b);
            }
        }
    }
    
    a = 0;
    b = 0;
    while(a < v1.size() && b < v2.size())
    {
        if(v1[a] == v2[b])
        {
            a++;
            b++;
        }
        else if(v1[a] < v2[b])
        {
            wyn.push_back(tr(2, v1[a]));
            // cout<<"- "<<v1[a].first<<" "<<v1[a].second<<"\n";
            a++;
        }
        else
        {
            wyn.push_back(tr(1, v2[b]));
            // cout<<"+ "<<v2[b].first<<" "<<v2[b].second<<"\n";
            b++;
        }
    }
    for(int i=a; i<v1.size(); i++) wyn.push_back(tr(2, v1[i])); // cout<<"- "<<v1[i].first<<" "<<v1[i].second<<"\n";
    for(int i=b; i<v2.size(); i++) wyn.push_back(tr(1, v2[i])); // cout<<"+ "<<v2[i].first<<" "<<v2[i].second<<"\n";
    
    // post
    for(int i=1; i<=n; i++) col[i] = 0;
    col[1] = 1;
    q.push(1);
    while(!q.empty())
    {
        a = q.front();
        q.pop();
        if(col[a] > 2) ord.push_back(a);
        for(int i=0; i<graf2[a].size(); i++)
        {
            b = graf2[a][i];
            if(col[b] == 0)
            {
                col[b] = col[a] + 1;
                q.push(b);
            }
        }
    }
    for(int i=ord.size()-1; i>=0; i--) wyn.push_back(tr(2, par(1, ord[i]))); //cout<<"- 1 "<<ord[i]<<"\n";
    
    // cout
    cout<<wyn.size()<<"\n";
    for(int i=0; i<wyn.size(); i++)
    {
        if(wyn[i].first == 1) cout<<"+ ";
        else cout<<"- ";
        cout<<wyn[i].second.first<<" "<<wyn[i].second.second<<"\n";
    }
    return 0;
}