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
#include <cstdio>
#include <cstdlib>

typedef struct{int p; int q;} edge;

int asc(const void *a, const void *b)
{
  int p = ((edge *)a)->p - ((edge *)b)->p;
  int q = ((edge *)a)->q - ((edge *)b)->q;
  return p+q*(p==0);
}

edge e[2][100000];
int f[2][30001];
int o[2][30000];
int s[30000];
char h[30000];
char v[30000];

int main()
{
  int n, m[2], p, q, r[2];
  scanf("%i", &n);
  for (int j = 0; j<2; j++)
  {
    scanf("%i", &m[j]);
    f[j][n] = m[j]*2;
    for (int i = 0; i<n; i++) h[i] = 0, v[i] = 0;
    for (int i = 0; i<f[j][n]; i+=2)
    {
      scanf("%i%i", &p, &q);
      e[j][i].p = --p, e[j][i].q = --q;
      e[j][i+1].p = q, e[j][i+1].q = p;
      if (!p || !q) h[p+q] = 1;
    }
    qsort(e[j], f[j][n], sizeof(*e[j]), asc);
    for (int i = f[j][n]-1; i>=0; i--) f[j][e[j][i].p] = i;
    p = 0;
    q = 0;
    r[j] = 0;
    v[p] = 1, s[p++] = 0;
    while (q<p)
    {
      int w = s[q++];
      for (int i = f[j][w]; i < f[j][w+1]; i++)
      {
        if (!v[e[j][i].q])
        {
          v[e[j][i].q] = 1;
          if (!h[e[j][i].q]) o[j][r[j]++] = e[j][i].q;
          s[p++] = e[j][i].q;
        }
      }
    }
  }
  printf("%i\n", r[0] + m[0]-f[0][1] + r[1] + m[1]-f[1][1]);
                            for (int i = 0; i<r[0]; i++)                                   printf("+ 1 %i\n", o[0][i]+1);
  for (int j = 0; j<2; j++) for (int i = f[j][1]; i<f[j][n]; i++) if (e[j][i].p<e[j][i].q) printf("%c %i %i\n", "-+"[j], e[j][i].p+1, e[j][i].q+1);
                            for (int i = r[1]-1; i>=0; i--)                                printf("- 1 %i\n", o[1][i]+1);
  return 0;
}