Problem:
 Score : 900 points    Problem Statement You are given an undirected graph consisting of N vertices and M edges.
The vertices are numbered 1 to N , and the edges are numbered 1 to M .
In addition, each vertex has a label, A or B . The label of Vertex i is s_i .
Edge i bidirectionally connects vertex a_i and b_i .  The phantom thief Nusook likes to choose some vertex as the startpoint and traverse an edge zero or more times.
Today, he will make a string after traveling as above, by placing the labels of the visited vertices in the order visited, beginning from the startpoint.  For example, in a graph where Vertex 1 has the label A and Vertex 2 has the label B , if Nusook travels along the path 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 2 , the resulting string is ABABB .  Determine if Nusook can make all strings consisting of A and B .      Constraints  2 \leq N \leq 2 \times 10^{5}  1 \leq M \leq 2 \times 10^{5}  |s| = N  s_i is A or B .  1 \leq a_i, b_i \leq N  The given graph may NOT be simple or connected.         Input Input is given from Standard Input in the following format:  N  M  s  a_1  b_1  :  a_{M}  b_{M}       Output If Nusook can make all strings consisting of A and B , print Yes ; otherwise, print No .        Sample Input 1 2 3
AB
1 1
1 2
2 2      Sample Output 1 Yes   Since Nusook can visit Vertex 1 and Vertex 2 in any way he likes, he can make all strings consisting of A and B .           Sample Input 2 4 3
ABAB
1 2
2 3
3 1      Sample Output 2 No   For example, Nusook cannot make BB .  The given graph may not be connected.           Sample Input 3 13 23
ABAAAABBBBAAB
7 1
10 6
1 11
2 10
2 8
2 11
11 12
8 3
7 12
11 2
13 13
11 9
4 1
9 7
9 6
8 13
8 6
4 10
8 7
4 3
2 1
8 12
6 9      Sample Output 3 Yes       Sample Input 4 13 17
BBABBBAABABBA
7 1
7 9
11 12
3 9
11 9
2 1
11 5
12 11
10 8
1 11
1 8
7 7
9 10
8 8
8 12
6 2
13 11      Sample Output 4 No

Solution (Python):

from collections import deque

N, M = map(int, input().split())
s = list(input())
s_ = []
for c in s:
    s_.append(c)


G = dict()
for i in range(1, N+1):
    G[i] = dict()

for _ in range(M):
    a, b = map(int, input().split())
    G[a][b] = 1
    G[b][a] = 1
    

queue = deque()
go = True

As = [0]*N
Bs = [0]*N

for i in range(1, N+1):
    if s[i-1] != "C":
        a = 0
        b = 0
        for k in G[i].keys():
            v = s_[k-1]
            if v == "A":
                a += 1
            elif v == "B":
                b += 1
        As[i-1] = a
        Bs[i-1] = b
        if a*b == 0:
            queue.append(i)
            s[i-1] = "C"

while len(queue) > 0:
    j = queue.popleft()
    for i in G[j].keys():
        if s[i-1] != "C":
            if s_[j-1] == "A":
                As[i-1] -= 1
            else:
                Bs[i-1] -= 1
            if As[i-1] * Bs[i-1] == 0:
                queue.append(i)
                s[i-1] = "C"

if "A" in s and "B" in s:
    print("Yes")
else:
    print("No")

Solution (Python):
from sys import stdin
from itertools import repeat
def main():
    n, m = map(int, stdin.readline().split())
    s = raw_input().strip()
    dat = map(int, stdin.read().split(), repeat(10, 2 * m))
    e = [[set(), set()] for i in xrange(n)]
    for i in xrange(2 * m):
        dat[i] -= 1
    for i in xrange(m):
        x, y = dat[i*2], dat[i*2+1]
        e[x][s[y]=='B'].add(i)
        e[y][s[x]=='B'].add(i)
    st = []
    pu = st.append
    po = st.pop
    d = [0] * n
    for i in xrange(n):
        if not e[i][0] or not e[i][1]:
            pu(i)
            d[i] = 1
    while st:
        z = po()
        for j in xrange(2):
            for i in e[z][j]:
                x, y = dat[i*2], dat[i*2+1]
                if x == y:
                    continue
                if x == z:
                    x, y = y, x
                e[x][s[y]=='B'].discard(i)
                if not e[x][s[y]=='B'] and not d[x]:
                    d[x] = 1
                    pu(x)
            e[z][j].clear()
    for i in xrange(n):
        if e[i][0] and e[i][1]:
            print 'Yes'
            return
    print 'No'
main()