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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <bits/stdc++.h>
using namespace std;

#define mp(a,b) make_pair(a,b)
#define ff first
#define setp(a) setprecision(a)<<fixed
#define ss second
#define fori(v) for(int i=0; i<v; i++)
#define forj(v) for(int j=0; j<v; j++)
#define fork(v) for(int k=0; k<v; k++)
#define forl(v) for(int l=0; l<v; l++)
#define fort(v) for(int t=0; t<v; t++)
#define forz(v) for(int z=0; z<v; z++)
#define forx(v) for(int x=0; x<v; x++)
#define fory(v) for(int y=0; y<v; y++)
#define ll long long
#define lll __int128
#define ld long double
#define pb(a) push_back(a)
// #define cout out
// #define cin in
ll inf = (ll)pow(10,18);
ll modulo = 998244353;
ld eps = 1e-13;
ifstream in;
ofstream out;

vector<vector<ll> > ans;
set<pair<ll, ll> > edg1, edg2;

void dfs1(ll hd, vector<vector<ll> >& g, set<ll>& seen){
      // 1) add all edges from 1 to all nodes in the order of dfs in tree1 iff not present
      // already in tree1.
      for(auto& hr : g[hd]){
            if(seen.find(hr)!=seen.end()){
                  continue;
            }
            if(edg1.find(mp(0, hr)) == edg1.end()){
                  ans.pb(vector<ll>({1, 0, hr}));
                  edg1.insert(mp(0, hr));
            }
            seen.insert(hr);
            dfs1(hr, g, seen);
      }
}

void add(){
      // 2) add all the edges that are missing in tree1 (e.g. tree2 \ tree1, they are 
      // in tree2 but not in tree1 ). These edges can be added in any order.
      // After this step tree1 is a superset of tree2. 
                              
      for(auto& el : edg2){
            if(edg1.find(el) == edg1.end()){
                  ans.pb(vector<ll>({1, el.ff, el.ss}));
                  edg1.insert(el);
            }
      }
}

void rem(){
      // 3) now first remove all the edges that are not of the form 1 - x,
      // that were part of original tree1, that are no longer needed
      // cuz they are not present in tree2. These edges can be removed in any order.

      vector<pair<ll, ll> > del;
      for(auto& el : edg1){
            if(el.ff != 0 && edg2.find(el) == edg2.end()){
                  ans.pb(vector<ll>({0, el.ff, el.ss}));
                  del.pb(el);
            }
      }
      for(auto& el : del){
            edg1.erase(el);
      }
}

void dfs4(ll hd, vector<vector<ll> >& g, set<ll>& seen){
      // 4) now we need to remove the unneeded edges of the form 1-x, the ones that were
      // artificially added, now do a dfs in tree2, and remove the unneeded artificially 
      // added edges of tree1 in reverse dfs order of tree2. 

      for(auto& hr : g[hd]){
            if(seen.find(hr) != seen.end()){
                  continue;
            }
            seen.insert(hr);
            dfs4(hr, g, seen);
            
            if(edg2.find(mp(0, hr)) == edg2.end()){
                  edg1.erase(mp(0, hr));
                  ans.pb(vector<ll>({0, 0, hr}));
            }
            
      }
}

void deal(){
      // 1) add all edges from 1 to all nodes in the order of dfs in tree1 iff not present
      // already in tree1.     
       
      // 2) add all the edges that are missing in tree1 (e.g. tree2 \ tree1, they are 
      // in tree2 but not in tree1 ). These edges can be added in any order.
      // After this step tree1 is a superset of tree2. 
      
      // 3) now first remove all the edges that are not of the form 1 - x,
      // that were part of original tree1, that are no longer needed
      // cuz they are not present in tree2. These edges can be removed in any order.
      
      // 4) now we need to remove the unneeded edges of the form 1-x, the ones that were
      // artificially added, now do a dfs in tree2, and remove the unneeded artificially 
      // added edges of tree1 in reverse dfs order of tree2. 
      
      ll n;
      cin>>n;
      ll m1;
      cin>>m1;
      
      vector<vector<ll> > g1(n), g2(n);
      
      fori(m1){
            ll ai, bi;
            cin>>ai>>bi;
            --ai, --bi;
            if(ai > bi){
                  swap(ai, bi);
            }
            g1[ai].pb(bi);
            g1[bi].pb(ai);
            edg1.insert(mp(ai, bi));
      }
      
      ll m2;
      cin>>m2;
      
      fori(m2){
            ll ai, bi;
            cin>>ai>>bi;
            --ai, --bi;
            if(ai > bi){
                  swap(ai, bi);
            }
            g2[ai].pb(bi);
            g2[bi].pb(ai);
            edg2.insert(mp(ai, bi));
      }
      
      {
            set<ll> seen;
            seen.insert(0);
            dfs1(0, g1, seen);
      }
      
      add();
      
      rem();
      
      {
            set<ll> seen;
            seen.insert(0);
            dfs4(0, g2, seen);
      }
      
      assert(edg1 == edg2);
      
      cout<<ans.size()<<'\n';
      
      for(auto& el : ans){
            if(el[0] == 0){
                  cout<<"- ";
            }
            else{
                  cout<<"+ ";
            }
            cout<<el[1]+1<<' '<<el[2]+1<<'\n';
      }
      
}

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