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
//Jakub Trela
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

vector<vector<int>> g1,g2;
set<pair<int,int>> s1,s2;
vector<bool> visited;

struct Odp{
    char c;
    int a,b;
};

vector<Odp> ans1,ans2;

void dfs1(int w){
    visited[w]=1;
    if(w!=1 && s1.find({1,w})==s1.end()){
        ans1.push_back({'+',1,w});
    }
    for(int v:g1[w]){
        if(visited[v])continue;
        dfs1(v);
    }
}
void dfs2(int w){
    visited[w]=1;
    if(w!=1 && s2.find({1,w})==s2.end()){
        ans2.push_back({'-',1,w});
    }
    for(int v:g2[w]){
        if(visited[v])continue;
        dfs2(v);
    }
}

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

    int n,m1,m2;
    cin>>n>>m1;

    g1.resize(n+1);
    g2.resize(n+1);

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

    cin>>m2;

    for(int i=0;i<m2;i++){
        int a,b;
        cin>>a>>b;
        g2[a].push_back(b);
        g2[b].push_back(a);
        s2.insert({a,b});
        s2.insert({b,a});
    }

    visited.clear();
    visited.resize(n+1);
    dfs1(1);

    for(auto x:s1){
        if(x.first!=1 && x.second!=1 && x.second<x.first){
            ans1.push_back({'-',x.first,x.second});
        }
    }

    visited.clear();
    visited.resize(n+1);
    dfs2(1);

    for(auto x:s2){
        if(x.first!=1 && x.second!=1 && x.first<x.second){
            ans2.push_back({'+',x.first,x.second});
        }
    }
    cout<<ans1.size()+ans2.size()<<endl;
    for(int i=0;i<ans1.size();i++){
        cout<<ans1[i].c<<" "<<ans1[i].a<<" "<<ans1[i].b<<endl;
    }
    for(int i=ans2.size()-1;i>=0;i--){
        cout<<ans2[i].c<<" "<<ans2[i].a<<" "<<ans2[i].b<<endl;
    }

    return 0;
}