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
#include "bits/stdc++.h" // Ignacy Boehlke
using namespace std;     // XIII LO Szczecin
auto operator<<(auto&o,auto p)->decltype(p.first,o){return o<<'{'<<p.first<<", "<<p.second<<'}';}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<'{';int i=2;for(auto e:x)o<<(", ")+i<<e,i=0;return o<<'}';}
#ifdef DEBUG
#define PF(x...)fprintf(stderr,x)
#define LOG(x...)cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<'\n';}(x)
#else
#define PF(...)(void)0
#define LOG(...)(void)0
#endif
#define FOR(a,b,c)for(int a=(b);a<=(c);++a)
#define REP(a,b)FOR(a,0,(b)-1)
#define ALL(x)(x).begin(), (x).end()
#define fi first
#define se second
using ll=int64_t;

int main() {
        cin.tie(0)->sync_with_stdio(0);
        int n;
        cin >> n;

        auto e = [](int a, int b) {if (a > b) swap(a, b); return (a << 15) | b;};
        auto get = [](int x) {return array{x >> 15, x & 0x7fff};};

        auto read = [&]() {
                unordered_set<int> edg;
                int m;
                cin >> m;
                REP(i, m) {
                        int a, b;
                        cin >> a >> b; --a; --b;
                        edg.insert(e(a, b));
                }
                return edg;
        };
        auto edg = read();

        vector<array<int, 2>> added, removed;
        auto connect = [&](int a, int b) {
                if (edg.insert(e(a, b)).se)
                        added.push_back({a, b});
        };
        auto add = [&](int x) {
                if (edg.insert(x).se)
                        added.push_back(get(x));
        };
        auto rm = [&](int x) {
                edg.erase(x);
                auto [a, b] = get(x);
                removed.push_back({a, b});
        };

        auto mkgraph = [&]() {
                vector<vector<int>> graph(n);
                for (int x : edg) {
                        auto [a, b] = get(x);
                        graph[a].push_back(b);
                        graph[b].push_back(a);
                }
                return graph;
        };

        auto graph = mkgraph();
        vector<bool> vis(n);
        auto dfs = [&](auto &self, int v) -> void {
                if (v) connect(0, v);
                vis[v] = true;
                for (int u : graph[v]) if (!vis[u])
                        self(self, u);
        };
        dfs(dfs, 0);

        auto goal = read();
        for (int x : goal) if (!edg.contains(x)) add(x);
        LOG(edg);

        vector<int> torm, roots;
        for (int x : edg) {
                if (x >> 15) {
                        if (!goal.contains(x)) torm.push_back(x);
                } else if (goal.contains(x))
                        roots.push_back(x & 0x7fff);
        }
        for (int x : torm) rm(x);
        LOG(roots);

        graph = mkgraph();
        vis.assign(n, false);
        vis[0] = true;
        auto dfs2 = [&](auto &self, int v) -> void {
                LOG(v);
                vis[v] = true;
                for (int u : graph[v]) if (!vis[u])
                        self(self, u);
                int x = e(0, v);
                if (!goal.contains(x)) rm(x);
        };

        for (int v : roots) if (!vis[v]) dfs2(dfs2, v);

        cout << ssize(added) + ssize(removed) << '\n';
        for (auto [a, b] : added)
                cout << "+ " << a + 1 << ' ' << b + 1 << '\n';
        for (auto [a, b] : removed)
                cout << "- " << a + 1 << ' ' << b + 1 << '\n';
}