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
#include <iostream>
#include <algorithm>
#include <vector>
void dfs(int v, std::vector<std::vector<int>> &adj, bool visited[], std::vector<std::pair<int,int>> &toModify){
    std::sort(adj[v].begin(), adj[v].end());
    visited[v] = true;
    if (v!=0 && adj[v][0]!= 0){
        toModify.push_back(std::make_pair(0, v));
    }
    for (int i = 0; i< adj[v].size(); i++){
        if (!visited[adj[v][i]]){
            visited[adj[v][i]] = true;
            dfs(adj[v][i], adj, visited, toModify);
        }
    }
}

bool visited1[30001], visited2[30001];
std::vector<std::pair<int, int>> toAdd, toRemove;
int main(){
    int n, m1, m2;
    std::cin>>n;
    std::vector<std::vector<int>> adj1(n);
    std::cin>>m1;
    std::vector<std::pair<int, int>> edges1;
    std::vector<std::pair<int, int>> edges2;

    for(int i=0; i<m1; i++){
        int a, b;
        std::cin>>a>>b;
        a--, b--;
        if (a!=0 && b!=0)
            edges1.push_back(std::make_pair(a, b));
        adj1[a].push_back(b);
        adj1[b].push_back(a);
    }
    dfs(0, adj1, visited1, toAdd);
    
    std::cin>>m2;
    std::vector<std::vector<int>> adj2(n);
    for(int i=0; i<m2; i++){
        int a, b;
        std::cin>>a>>b;
        a--, b--;
        
        if (a!=0 && b!=0){
            edges2.push_back(std::make_pair(a, b));
        }
        adj2[a].push_back(b);
        adj2[b].push_back(a);
    }
    dfs(0, adj2, visited2, toRemove);
    std::cout<<toAdd.size()+edges1.size()+edges2.size()+toRemove.size()<<"\n";

    for (int i = 0 ;i<toAdd.size(); i++){
        std::cout<<"+ "<<toAdd[i].first+1<<" "<<toAdd[i].second+1<<"\n";
    }
    for (int i = 0; i<edges1.size(); i++){
        std::cout<<"- "<<edges1[i].first+1<<" "<<edges1[i].second+1<<"\n";
    }
    for (int i =0; i< edges2.size(); i++){
        std::cout<<"+ "<<edges2[i].first+1<<" "<<edges2[i].second+1<<"\n";
    }
    for(int i=toRemove.size()-1; i>=0; i--){
        std::cout<<"- "<<toRemove[i].first+1<<" "<<toRemove[i].second+1<<"\n";
    }

}