A-Z Graph (Codeforces 1494E)
Tags: Others, hashing

You are given a directed graph consisting of $$$n$$$ vertices. Each directed edge (or arc) labeled with a single character. Initially, the graph is empty.You should process $$$m$$$ queries with it. Each query is one of three types:   "$$$+$$$ $$$u$$$ $$$v$$$ $$$c$$$" — add arc from $$$u$$$ to $$$v$$$ with label $$$c$$$. It's guaranteed that there is no arc $$$(u, v)$$$ in the graph at this moment;  "$$$-$$$ $$$u$$$ $$$v$$$" — erase arc from $$$u$$$ to $$$v$$$. It's guaranteed that the graph contains arc $$$(u, v)$$$ at this moment;  "$$$?$$$ $$$k$$$" — find the sequence of $$$k$$$ vertices $$$v_1, v_2, \dots, v_k$$$ such that there exist both routes $$$v_1 \to v_2 \to \dots \to v_k$$$ and $$$v_k \to v_{k - 1} \to \dots \to v_1$$$ and if you write down characters along both routes you'll get the same string. You can visit the same vertices any number of times. 

Input: The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 2 \cdot 10^5$$$) — the number of vertices in the graph and the number of queries.The next $$$m$$$ lines contain queries — one per line. Each query is one of three types:   "$$$+$$$ $$$u$$$ $$$v$$$ $$$c$$$" ($$$1 \le u, v \le n$$$; $$$u \neq v$$$; $$$c$$$ is a lowercase Latin letter);  "$$$-$$$ $$$u$$$ $$$v$$$" ($$$1 \le u, v \le n$$$; $$$u \neq v$$$);  "$$$?$$$ $$$k$$$" ($$$2 \le k \le 10^5$$$). It's guaranteed that you don't add multiple edges and erase only existing edges. Also, there is at least one query of the third type.

Output: For each query of the third type, print YES if there exist the sequence $$$v_1, v_2, \dots, v_k$$$ described above, or NO otherwise.

Note: In the first query of the third type $$$k = 3$$$, we can, for example, choose a sequence $$$[1, 2, 3]$$$, since $$$1 \xrightarrow{\text{a}} 2 \xrightarrow{\text{b}} 3$$$ and $$$3 \xrightarrow{\text{a}} 2 \xrightarrow{\text{b}} 1$$$.In the second query of the third type $$$k = 2$$$, and we can't find sequence $$$p_1, p_2$$$ such that arcs $$$(p_1, p_2)$$$ and $$$(p_2, p_1)$$$ have the same characters.In the third query of the third type, we can, for example, choose a sequence $$$[1, 2, 3, 2, 1]$$$, where $$$1 \xrightarrow{\text{a}} 2 \xrightarrow{\text{b}} 3 \xrightarrow{\text{d}} 2 \xrightarrow{\text{c}} 1$$$.

Sample Inputs:
3 11
+ 1 2 a
+ 2 3 b
+ 3 2 a
+ 2 1 b
? 3
? 2
- 2 1
- 3 2
+ 2 1 c
+ 3 2 d
? 5

Sample Outputs:
YES
NO
YES

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    (n, m) = map(int, input().split())
    e = dict()
    same = 0
    diff = 0
    res = []
    for i in range(m):
        a = input().split()
        c = a[0]
        if c == '+':
            u = int(a[1])
            v = int(a[2])
            c = a[3]
            z = e.get((v, u), None)
            if z == c:
                same += 1
            elif z is not None:
                diff += 1
            e[u, v] = c
        elif c == '-':
            u = int(a[1])
            v = int(a[2])
            c = e[u, v]
            del e[u, v]
            z = e.get((v, u), None)
            if z == c:
                same -= 1
            elif z is not None:
                diff -= 1
        else:
            c = int(a[1])
            if c % 2 == 1:
                if diff + same > 0:
                    res.append('YES')
                else:
                    res.append('NO')
            elif same > 0:
                res.append('YES')
            else:
                res.append('NO')
    print('\n'.join(res))
solve()

Solution (Python):
def solve():
    (n, m) = map(int, input().split())
    e = dict()
    same = 0
    diff = 0
    res = []
    for i in range(m):
        a = input().split()
        c = a[0]
        if c == '+':
            u = int(a[1])
            v = int(a[2])
            c = a[3]
            z = e.get((v, u), None)
            if z == c:
                same += 1
            elif z is not None:
                diff += 1
            e[u, v] = c
        elif c == '-':
            u = int(a[1])
            v = int(a[2])
            c = e[u, v]
            del e[u, v]
            z = e.get((v, u), None)
            if z == c:
                same -= 1
            elif z is not None:
                diff -= 1
        else:
            c = int(a[1])
            if c % 2 == 1:
                if diff + same > 0:
                    res.append('YES')
                else:
                    res.append('NO')
            elif same > 0:
                res.append('YES')
            else:
                res.append('NO')
    print('\n'.join(res))
solve()

Solution (Python):
def solve():
    (n, m) = map(int, input().split())
    e = dict()
    same = 0
    diff = 0
    res = []
    for i in range(m):
        a = input().split()
        c = a[0]
        if c == '+':
            u = int(a[1])
            v = int(a[2])
            c = a[3]
            z = e.get((v, u), None)
            if z == c:
                same += 1
            elif z is not None:
                diff += 1
            e[u, v] = c
        elif c == '-':
            u = int(a[1])
            v = int(a[2])
            c = e[u, v]
            del e[u, v]
            z = e.get((v, u), None)
            if z == c:
                same -= 1
            elif z is not None:
                diff -= 1
        else:
            c = int(a[1])
            if c % 2 == 1:
                res.append('YES' if diff + same > 0 else 'NO')
            else:
                res.append('YES' if same > 0 else 'NO')
    print('\n'.join(res))
solve()