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
import queue
import sys
n = int(input())
if n == 2:
    print(0)
    sys.exit(0)

def read_graph():
    m1 = int(input())
    adj = [set() for _ in range(n)]
    for _ in range(m1):
        a, b = [int(x) for x in input().split()]
        a -= 1
        b -= 1
        adj[a].add(b)
        adj[b].add(a)
    return adj

g1 = read_graph()
g2 = read_graph()

def to_convert(before, after):
    to_add = [set() for _ in range(n)]
    for a in range(n):
        for i in after[a] - before[a]:
            if i > a:
                to_add[a].add(i)
        #print("to add[",a,"]", to_add[a], file=sys.stderr)

    extra_connections = []

    prev = [-1 for _ in range(n)]
    for from_ in range(n):
        to_ = set(to_add[from_])
        if not to_:
            continue
        # TODO: this is likely too slow
        q = queue.Queue()
        q.put(from_)
        prev[from_] = from_
        mark_back = [from_]
        while to_:
            top = q.get()
            if top in to_:
                to_.remove(top)
            for next_ in before[top]:
                if prev[next_] == -1:
                    prev[next_] = top
                    q.put(next_)
                    mark_back.append(next_)

        # Can I update to add so 
        for neigh in to_add[from_]:
            #print("from", from_, neigh, file=sys.stderr)
            path = neigh
            temp_connections = []
            while prev[path] != from_:
                if path > from_:
                    temp_connections.append((from_, path))
                else:
                    temp_connections.append((path, from_))
                next_ = prev[path]
                prev[path] = from_
                path = next_
            #print("adding extra connections", extra_connections, file=sys.stderr)
            extra_connections.extend(reversed(temp_connections))
        for i in mark_back:
            prev[i] = -1

    return extra_connections

def to_join(one, two):
    to_add1 = to_convert(one, two)
    #print("toadd1", to_add1, file=sys.stderr)
    to_add2 = to_convert(two, one)
    #print("toadd2", to_add2, file=sys.stderr)
    already_added = set()
    all_to_add = []
    for a, b in to_add1 + to_add2:
        if a > b:
            a, b = b, a
        if b not in one[a] and (a, b) not in already_added:
            all_to_add.append((a, b))
            already_added.add((a, b))

    return all_to_add

positive = to_join(g1, g2)
negative = list(reversed(to_join(g2, g1)))

print(len(positive) + len(negative))
if positive:
    print("\n".join([f"+ {a + 1} {b + 1}" for a, b in positive]))
if negative:
    print("\n".join([f"- {a + 1} {b + 1}" for a, b in negative]))