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
debug_mode = False
def t_int(x):
    return [int(c) for c in x.split(" ") if c != " " and c != ""]

n, q = input().split(" ")
n, q = int(n), int(q)

events = []
for i in range(q):
    events.append(input().split())

def add_edge(a, b, states, edges):
    states[a] = "?"
    states[b] = "?"
    if a == b:
        set_vertex_value(a, 1, states, edges, True)
    elif a in states and states[a] == 1:
        states[b] = 1
    elif b in states and states[b] == 1:
        states[a] = 1
    else:
        new_edge = (a, b)
        edges.add(new_edge)
        # print(f"Will check for knowledge for {a} and {b}: edges: {edges} states: {states}")
        check_for_knowledge(a, states, edges)

def set_vertex_value(v, value, states, edges, remove_edges):
    states[v] = value
    edges_to_remove = set()
    if remove_edges:
        for edge in edges:
            if v in edge:
                edges_to_remove.add(edge)
        for edge in edges_to_remove:
            edges.remove(edge)

def parse_remove_computer(c, states, edges):
    set_vertex_value(c, 0, states, edges, True)

def check_for_knowledge(d, states, edges):
    queue = [d]
    component = {d}
    edges_in_component = set()
    while len(queue) > 0:
        current = queue.pop(0)
        for edge in edges:
            if current in edge:
                other = edge[0] if edge[0] != current else edge[1]
                if other not in component:
                    component.add(other)
                    queue.append(other)

    for edge in edges:
        if edge[0] in component and edge[1] in component:
            edges_in_component.add(edge)

    if debug_mode:
        print(f"for {d} component: {component} edges_in_component: {edges_in_component} \n")

    if len(edges_in_component) == 0 and sum([states[v] for v in component if states[v] != "?"]) == 0:
        if debug_mode:
            print(f"component: {component} detected as 0s")
        for vertex in component:
            set_vertex_value(vertex, 0, states, edges, False)
            return "0"
    elif len(edges_in_component) == len(component):
        if debug_mode:
            print(f"component: {component} detected as 1s")
        for vertex in component:
            if debug_mode:
                print(f"setting {vertex} to 1 | states: {states}")
            set_vertex_value(vertex, 1, states, edges, True)
        return "1"
    else:
        return "?"

def parse_question(d, states, edges):
    if d not in states:
        return "0"
    elif d in states and states[d] != "?":
        return str(states[d])
    else:
        return check_for_knowledge(d, states, edges)

def solve_1A_graph(events):
    states = {}
    edges = set()

    ans = ""
    i = 0
    for event in events:
        if event[0] == "+":
            add_edge(int(event[1]), int(event[2]), states, edges)
        elif event[0] == "-":
            parse_remove_computer(int(event[1]), states, edges)
        elif event[0] == "?":
            ans += parse_question(int(event[1]), states, edges)
        if debug_mode:
            print(f" event: {event}")
            print(f" states: {states} \n edges: {edges}  \n")

            # if event[0] == "?":
            #     print(f" answer: {ans}")
        if debug_mode:
            if event[0] == "?":
                print(f"answer = {ans[-1]} expected")
            print("====================================")
        # print("====================================")
    return ans

print(solve_1A_graph(events))