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

using namespace std;

typedef long long ll;

struct Point {
    char c;
    ll x,y;
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n;
    cin>>n;
    vector <Point> res;
    res.reserve(200000);
    vector <vector <ll> > graph(n+1);
    map <pair <ll,ll>, bool> M;
    ll m;
    cin>>m;
    for(ll i=0;i<m;i++) {
        ll a,b;
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
        M[{a,b}]=1;
        M[{b,a}]=1;
    }
    vector <ll> vis(n+1,0);
    queue <ll> q;
    q.push(1);
    vis[1]=1;
    while(!q.empty()) {
        ll p=q.front();
        q.pop();
        for(ll i=0;i<graph[p].size();i++) {
            ll x=graph[p][i];
            if(vis[x]==0) {
                if(M[{1,x}]==0) {
                    res.push_back({'+',1,x});
                    graph[1].push_back(x);
                    graph[x].push_back(1);
                    M[{1,x}]=1;
                    M[{x,1}]=1;
                }
                vis[x]=1;
                q.push(x);
            }
        }
    }
    cin>>m;
    map <pair <ll,ll>, bool> M1;
    for(ll i=0;i<m;i++) {
        ll a,b;
        cin>>a>>b;
        M1[{a,b}]=1;
        M1[{b,a}]=1;
        if(M[{a,b}]==0) {
            res.push_back({'+',a,b});
            graph[a].push_back(b);
            graph[b].push_back(a);
            M[{a,b}]=1;
            M[{b,a}]=1;
        }
    }
    for(ll i=1;i<=n;i++) {
        for(ll j=0;j<graph[i].size();j++) {
            ll x=graph[i][j];
            if(M[{i,x}]==1 && M1[{i,x}]==0) {
                res.push_back({'-',i,x});
                M[{i,x}]=0;
                M[{x,i}]=0;
            }
        }
    }
    cout<<res.size()<<endl;
    for(ll i=0;i<res.size();i++) {
        cout<<res[i].c<<" "<<res[i].x<<" "<<res[i].y<<endl;
    }
    return 0;
}