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 long long ll;
typedef pair<int, int> pii;

const int N = 1e5+10;

set<pii> s1, s2;

int n, m1, m2;

vector<pii> mv;

set<int> G[N];

bool vis[N];
void dfs(int v) {
    vis[v]=true;
    
    if (v != 1 && s1.find({v, 1}) == s1.end()) {
        mv.push_back({1, v});
        s1.insert({1, v});
        s1.insert({v, 1});
        G[1].insert(v);
        G[v].insert(1);
    }

    for (auto u : G[v]) {
        if (vis[u]) continue;
        dfs(u);
    }
}

void rem(int v) {
    vis[v]=true;

    for (auto u : G[v]) {
        if (vis[u]) continue;
        rem(u);
    }

    if (s2.find({1, v}) == s2.end() && v != 1) {
        mv.push_back({-1, -v});
    }
}

void solve() {
    cin>>n;

    cin>>m1;
    for (int i=1; i<=m1; ++i) {
        int a, b; cin>>a>>b;
        s1.insert({a, b});
        s1.insert({b, a});
        G[a].insert(b);
        G[b].insert(a);
    }

    cin>>m2;
    for (int i=1; i<=m2; ++i) {
        int a, b; cin>>a>>b;
        s2.insert({a, b});
        s2.insert({b, a});
    }

    // choose vertex 1 as "source"
    dfs(1);

    // add all needed edges
    for (auto u : s2) {
        if (s1.find(u) == s1.end()) {
            mv.push_back(u);
            G[u.first].insert(u.second);
            G[u.second].insert(u.first);
            s1.insert(u);
            s1.insert({u.second, u.first});
        }
    }

    // remove all edges needed
    for (auto u : s1) {
        if (u.first == 1 || u.second == 1) continue;
        if (s2.find(u) == s2.end()) {
            mv.push_back({-u.first, -u.second});
            s2.insert(u);
            s2.insert({u.second, u.first});
            G[u.first].erase(u.second);
            G[u.second].erase(u.first);
        }
    }

    // erase all bad (1, x) edges
    memset(vis, false, sizeof(vis));
    rem(1);

    assert((int)mv.size() <= 200'000);
    cout<<mv.size()<<"\n";
    for (auto u : mv) {
        if (u.first > 0) cout<<"+ "<<u.first<<" "<<u.second<<"\n";
        else cout<<"- "<<(-u.first)<<" "<<(-u.second)<<"\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int t=1; //cin>>t;
    while (t--) solve();
}