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
#include <iostream>
#include <set>
#include <vector>
using namespace std;

const int N=30100;

set<pair<int,int>> orginal, wanted, to_added, to_delete;

vector<vector<int>> g1(N),g2(N);
vector<pair<char,pair<int,int>>> res;
bool visited[N];

void dfs_add_1(int s)
{
    visited[s]=1;
    if(s!=1)
    {
        if(!orginal.count({1,s}))
            res.push_back({'+',{1,s}});
    }
    for(int i = 0 ;i <g1[s].size(); i ++)if(!visited[g1[s][i]])
        dfs_add_1(g1[s][i]);
}

void dfs_delete_1(int s)
{
    visited[s]=1;
    for(int i = 0 ;i <g2[s].size(); i ++)if(!visited[g2[s][i]])
        dfs_delete_1(g2[s][i]);
    if(s!=1)
    {
        if(!wanted.count({1,s}))
            res.push_back({'-',{1,s}});
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    int m1,m2;
    cin>>m1;
    for(int i = 0 ;i < m1 ;i ++)
    {
        int a,b;
        cin>>a>>b;
        if(a>b)swap(a,b);
        g1[a].push_back(b);
        g1[b].push_back(a);
        orginal.insert({a,b});
    }
    cin>>m2;
    for(int i = 0 ;i < m2 ;i ++)
    {
        int a,b;
        cin>>a>>b;
        if(a>b)swap(a,b);
        g2[a].push_back(b);
        g2[b].push_back(a);
        wanted.insert({a,b});
        if(!orginal.count({a,b}))
            to_added.insert({a,b});
    }
    for(int i = 1 ;i <=n ;i ++)
    {
        for(int j = 0 ;j <g1[i].size();j++)if(g1[i][j]>i)
        {
            if(!wanted.count({i,g1[i][j]}))
                to_delete.insert({i,g1[i][j]});
        }
    }
    dfs_add_1(1);
    for(int i = 0 ;i <= n ;i ++)
        visited[i]=0;
    for(auto I : to_added)
    {
        if(I.first!=1)
            res.push_back({'+',{I.first,I.second}});
    }
    for(auto I : to_delete)
    {
        if(I.first!=1)
            res.push_back({'-',{I.first,I.second}});
    }
    dfs_delete_1(1);
    cout<<res.size()<<'\n';
    for(int i = 0 ;i <res.size();i++)
        cout<<res[i].first<<' '<<res[i].second.first<<' '<<res[i].second.second<<'\n';
}