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



Sample input:
2 3
AB
1 1
1 2
2 2


Sample output:
Yes

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(i) for i in input().split(' ')]
import sys
from collections import defaultdict
sys.setrecursionlimit(10**7)

s = input().strip()
ds = [defaultdict(set), defaultdict(set)]
starts = set()
for ll in sys.stdin:
    i, j = ll.strip().split(' ')
    i, j = int(i)-1, int(j)-1
    ds[0 if s[i] == s[j] else 1][str(0 if s[i] == s[j] else 1) + str(i)].add(str(1 if s[i] == s[j] else 0) + str(j))
    ds[0 if s[i] == s[j] else 1][str(0 if s[i] == s[j] else 1) + str(j)].add(str(1 if s[i] == s[j] else 0) + str(i))
    if s[i] == 'A' and s[j] == 'A':
        starts.add(str(0)+str(i))


checked = set()

path = set()
#path = []

def walk(i, depth):
    dd = ds[depth]
    checked.add(i)
    if len(dd[i]) == 0:
        return False
    r = False
    for item in dd[i]:
        if item in path:
            return True
        if item not in checked:
            path.add(item)
#            path.append(item)
            r = r or walk(item, (depth+1) % 2)
            path.remove(item)
#            path.pop()
    return r

result = False
for item in starts:
    if item not in checked:
        path.add(item)
#        path.append(item)
        result = result or walk(item, 0)
        path.remove(item)
#        path.pop()
if result:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(200000)


def add_link(a, b):
    la = links[a]
    i, j = [(0, 1), (1, 0)][s[b] == 'B']
    if not la[i] and la[j]:
        able[a] = True
    la[i].add(b)


def close(v, i):
    j = int(s[v] == 'B')
    for u in links[v][i].copy():
        if not able[u]:
            continue
        links[u][j].discard(v)
        if not links[u][j]:
            able[u] = False
            close(u, j ^ 1)


n, m = map(int, input().split())
s = input()
links = [[set(), set()] for _ in range(n)]
able = [False] * n
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    add_link(a, b)
    add_link(b, a)

for v in range(n):
    if able[v]:
        continue
    close(v, bool(links[v][1]))

print('Yes' if any(able) else 'No')

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(200000)


def add_link(a, b):
    la = links[a]
    i, j = [(0, 1), (1, 0)][s[b] == 'B']
    if not la[i] and la[j]:
        able[a] = True
    la[i].add(b)


def close(v, i):
    j = int(s[v] == 'B')
    for u in links[v][i].copy():
        links[u][j].discard(v)
        if not links[u][j]:
            able[u] = False
            close(u, j ^ 1)


n, m = map(int, input().split())
s = input()
links = [[set(), set()] for _ in range(n)]
able = [False] * n
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    add_link(a, b)
    add_link(b, a)

for v in range(n):
    if able[v]:
        continue
    close(v, bool(links[v][1]))

print('Yes' if any(able) else 'No')

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(i) for i in input().split(' ')]
import sys
from collections import defaultdict
sys.setrecursionlimit(100000)

s = input().strip()
ds = [defaultdict(set), defaultdict(set)]
starts = set()
for ll in sys.stdin:
    i, j = ll.strip().split(' ')
    i, j = int(i)-1, int(j)-1
    ds[0 if s[i] == s[j] else 1][str(0 if s[i] == s[j] else 1) + str(i)].add(str(1 if s[i] == s[j] else 0) + str(j))
    ds[0 if s[i] == s[j] else 1][str(0 if s[i] == s[j] else 1) + str(j)].add(str(1 if s[i] == s[j] else 0) + str(i))
    if s[i] == 'A' and s[j] == 'A':
        starts.add(str(0)+str(i))


checked = [set(), set()]

path = [set(), set()]
#path = []

def walk(i, depth):
    dd = ds[depth]
    checked[depth].add(i)
    if len(dd[i]) == 0:
        return False
    r = False
    for item in dd[i]:
        if item in path[depth]:
            return True
        if item not in checked[depth]:
            path[depth].add(item)
#            path.append(item)
            r = r or walk(item, (depth+1) % 2)
            path[depth].remove(item)
#            path.pop()
    return r

result = False
for item in starts:
    if item not in checked:
        path[0].add(item)
#        path.append(item)
        result = result or walk(item, 0)
        path[0].remove(item)
#        path.pop()
if result:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(i) for i in input().split(' ')]
import sys
from collections import defaultdict
sys.setrecursionlimit(100000)

s = input().strip()
ds = [defaultdict(set), defaultdict(set)]
starts = set()
for ll in sys.stdin:
    i, j = ll.strip().split(' ')
    i, j = int(i)-1, int(j)-1
    ds[0 if s[i] == s[j] else 1][str(0 if s[i] == s[j] else 1) + str(i)].add(str(1 if s[i] == s[j] else 0) + str(j))
    ds[0 if s[i] == s[j] else 1][str(0 if s[i] == s[j] else 1) + str(j)].add(str(1 if s[i] == s[j] else 0) + str(i))
    if s[i] == 'A' and s[j] == 'A':
        starts.add(str(0)+str(i))


checked = set()

path = set()
#path = []

def walk(i, depth):
    dd = ds[depth]
    checked.add(i)
    if len(dd[i]) == 0:
        return False
    r = False
    for item in dd[i]:
        if item in path:
            return True
        if item not in checked:
            path.add(item)
#            path.append(item)
            r = r or walk(item, (depth+1) % 2)
            path.remove(item)
#            path.pop()
    return r

result = False
for item in starts:
    if item not in checked:
        path.add(item)
#        path.append(item)
        result = result or walk(item, 0)
        path.remove(item)
#        path.pop()
if result:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(i) for i in input().split(' ')]
import sys
from collections import defaultdict
sys.setrecursionlimit(100000)

s = input().strip()
d = {}
starts = set()
for s1 in 'AB':
    d[s1] = {}
    for s2 in 'AB':
        d[s1][s2] = defaultdict(set)
for ll in sys.stdin:
    i, j = ll.strip().split(' ')
    i, j = int(i)-1, int(j)-1
    d[s[i]][s[j]][i].add(j)
    d[s[j]][s[i]][j].add(i)
    if s[i] == 'A' and s[j] == 'A':
        starts.add(i)


checked = set()
def walk(i, depth, path):
    if depth == 0:
        dd = d['A']['A']
    elif depth == 1:
        dd = d['A']['B']
    elif depth == 2:
        dd = d['B']['B']
    else:
        dd = d['B']['A']
    checked.add(((depth)%4, i))
    if len(dd[i]) == 0:
        return False
    r = False
    for item in dd[i]:
        if ((depth+1)%4, item) in path:
            return True
        if ((depth+1)%4, item) not in checked:
#            r = r or walk(item, (depth+1) % 4, path + [((depth+1)%4 ,item)])
            path.add(((depth+1)%4, item))
            r = r or walk(item, (depth+1) % 4, path)
            path.remove(((depth+1)%4, item))
    return r

result = False
for item in starts:
    if item not in checked:
        result = result or walk(item, 0, {(0, item)})
#        result = result or walk(item, 0, [(0, item)])
if result:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(i) for i in input().split(' ')]
import sys
from collections import defaultdict
sys.setrecursionlimit(100000)

s = input().strip()
d = {}
starts = set()
for s1 in 'AB':
    d[s1] = {}
    for s2 in 'AB':
        d[s1][s2] = defaultdict(set)
for ll in sys.stdin:
    i, j = ll.strip().split(' ')
    i, j = int(i)-1, int(j)-1
    d[s[i]][s[j]][i].add(j)
    d[s[j]][s[i]][j].add(i)
    if s[i] == 'A' and s[j] == 'A':
        starts.add(i)


checked = set()
def walk(i, depth, path):
    if depth == 0:
        dd = d['A']['A']
    elif depth == 1:
        dd = d['A']['B']
    elif depth == 2:
        dd = d['B']['B']
    else:
        dd = d['B']['A']
    checked.add(((depth)%4, i))
    if len(dd[i]) == 0:
        return False
    r = False
    for item in dd[i]:
        if ((depth+1)%4, item) in path:
            return True
        if ((depth+1)%4, item) not in checked:
#            r = r or walk(item, (depth+1) % 4, path + [((depth+1)%4 ,item)])
            r = r or walk(item, (depth+1) % 4, path | {((depth+1)%4 ,item)})
    return r

result = False
for item in starts:
    if item not in checked:
        result = result or walk(item, 0, {(0, item)})
#        result = result or walk(item, 0, [(0, item)])
if result:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
s = input()

class Node:
    def __init__(self, node_id, label):
        self.node_id = node_id
        self.label = label
        self.from_links = set()
        self.to_links = set()
    def from_link(self, l):
        self.from_links.add(l)
    def to_link(self, l):
        self.to_links.add(l)
    def remove_from_link(self, l):
        self.from_links.remove(l)
    def remove_to_link(self, l):
        self.to_links.remove(l)
    def is_orphen(self):
        return not (self.to_links or self.from_links)
    def __repr__(self):
        return "Node<%d, %s>" % (self.node_id, label)

class Link:
    def __init__(self, frm, to):
        self.frm = frm
        self.to = to
        self.to_node = None
        self.frm_node = None
    def __repr__(self):
        return "Link<%s, %s>" % (self.frm_node, self.to_node)

class Graph:
    def __init__(self):
        self.nodes = dict()
        self.links = set()
    def add_node(self, node):
        self.nodes[node.node_id] = node
    def add_link(self, l):
        self.links.add(l)
        l.to_node = self.nodes[l.to]
        l.frm_node = self.nodes[l.frm]
        self.nodes[l.frm].from_link(l)
        self.nodes[l.to].to_link(l)
    def remove_link(self, l):
        self.links.remove(l)
        
        fn = self.nodes[l.frm]
        tn = self.nodes[l.to]
        fn.remove_from_link(l)
        tn.remove_to_link(l)
    def remove_node(self, n):
        del self.nodes[n.node_id]

g = Graph()
for i,label in enumerate(s,1):
    g.add_node(Node(i, label))
for _ in range(M):
    a,b = map(int, input().split())
    g.add_link(Link(a, b))
    g.add_link(Link(b, a))

touched = set(g.nodes.values())
while True:
    p_touched, touched = touched, set()
    for n in p_touched:
        lbl = set(m.to_node.label for m in n.from_links)
        if 'A' not in lbl or 'B' not in lbl:
            for l in n.to_links.copy():
                g.remove_link(l)
                touched.add(l.frm_node)
    if not touched:
        break
for n in set(g.nodes.values()):
    if n.is_orphen():
        g.remove_node(n)
print('Yes' if g.nodes else 'No')

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
s = input()

class Node:
    def __init__(self, node_id, label):
        self.node_id = node_id
        self.label = label
        self.from_links = set()
        self.to_links = set()
    def from_link(self, l):
        self.from_links.add(l)
    def to_link(self, l):
        self.to_links.add(l)
    def remove_from_link(self, l):
        self.from_links.remove(l)
    def remove_to_link(self, l):
        self.to_links.remove(l)
    def is_orphen(self):
        return not (self.to_links or self.from_links)
    def __repr__(self):
        return "Node<%d, %s>" % (self.node_id, label)

class Link:
    def __init__(self, frm, to):
        self.frm = frm
        self.to = to
        self.to_node = None
        self.frm_node = None
    def __repr__(self):
        return "Link<%s, %s>" % (self.frm_node, self.to_node)

class Graph:
    def __init__(self):
        self.nodes = dict()
        self.links = set()
    def add_node(self, node):
        self.nodes[node.node_id] = node
    def add_link(self, l):
        self.links.add(l)
        l.to_node = self.nodes[l.to]
        l.frm_node = self.nodes[l.frm]
        self.nodes[l.frm].from_link(l)
        self.nodes[l.to].to_link(l)
    def remove_link(self, l):
        self.links.remove(l)
        
        fn = self.nodes[l.frm]
        tn = self.nodes[l.to]
        fn.remove_from_link(l)
        tn.remove_to_link(l)
    def remove_node(self, n):
        del self.nodes[n.node_id]

g = Graph()
for i,label in enumerate(s,1):
    g.add_node(Node(i, label))
for _ in range(M):
    a,b = map(int, input().split())
    g.add_link(Link(a, b))
    g.add_link(Link(b, a))

while True:
    flag = False
    touched = set()
    for n in g.nodes.values():
        lbl = set(m.to_node.label for m in n.from_links)
        if 'A' not in lbl or 'B' not in lbl:
            for l in n.to_links.copy():
                g.remove_link(l)
                touched.add(l.frm_node)
                touched.add(l.to_node)
            if n.is_orphen():
                touched.add(n)
    if touched:
        for n in touched:
            if n.is_orphen():
                g.remove_node(n)
    else:
        break
print('Yes' if g.nodes else 'No')

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(i) for i in input().split(' ')]
import sys
from collections import defaultdict

s = input().strip()
ppp = set()
for ll in sys.stdin:
    i, j = ll.strip().split(' ')
    i, j = int(i)-1, int(j)-1
    ppp.add((i, j))
A = None
B = None
tmplA = None
tmplB = None
flag = False

ppps = [ppp]

while True:
    if flag:
        tta = len(A)
        ttb = len(B)
        if tta == 0 or ttb == 0:
            print('No')
            break
        if tmplA != None:
            if tmplA == tta and tmplB == ttb:
                print('Yes')
                break

    temp_ppp = set()
    ok = dict()
    ok['A'] = set()
    ok['B'] = set()
    rok = dict()
    rok['A'] = set()
    rok['B'] = set()
    for i, j in ppps[-1]:
        if flag:
            if i not in A and i not in B:
                continue
            if j not in A and j not in B:
                continue
        if s[i] == s[j]:
            ok[s[i]].add(i)
            ok[s[j]].add(j)
        else:
            rok[s[i]].add(i)
            rok[s[j]].add(j)
        temp_ppp.add((i, j))

    if flag:
        tmplA = tta
        tmplB = ttb
    A = ok['A'] & rok['A'] 
    B = ok['B'] & rok['B'] 
    ppps.append(temp_ppp)
    flag = True

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N,M = map(int, input().split())
s = input()

ten = []
for i in range(N):
    ten.append(s[i])

hen = []
for i in range(M):
    hen.append([int(j) for j in input().split()])

countnone = 0
beforenone = -1
while (countnone != beforenone):
    result = [set([]) for i in range(N)]

    for x,y in hen:
        result[x-1].add(ten[y-1])
        result[y-1].add(ten[x-1])

    i = 0
    for res in result:
        if (("A" not in res) or ("B" not in res)):
            ten[i] = None
        i = i + 1
    beforenone = countnone

    countnone = 0
    for t in ten:
        if t == None:
            countnone = countnone + 1

a = set()
for t in ten:
    a.add(t)

if (("A" not in a) or ("B" not in a)):
    print("No")
else:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
# C
N, M = map(int, input().split())
s = list(input())

# Graph
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
    
# clean up
go = True
while go:
    go = False
    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
            if a*b == 0:
                go = True
                s[i-1] = "C"

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

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(i) for i in input().split(' ')]
import sys
from collections import defaultdict
from copy import deepcopy

s = input().strip()
ppp = set()
for ll in sys.stdin:
    i, j = ll.strip().split(' ')
    i, j = int(i)-1, int(j)-1
    ppp.add((i, j))
A = None
B = None
tmplA = None
tmplB = None
flag = False

while True:
    if flag:
        tta = len(A)
        ttb = len(B)
        if tta == 0 or ttb == 0:
            print('No')
            break
        if tmplA != None:
            if tmplA == tta and tmplB == ttb:
                print('Yes')
                break

    temp_ppp = set()
    ok = dict()
    ok['A'] = set()
    ok['B'] = set()
    rok = dict()
    rok['A'] = set()
    rok['B'] = set()
    for i, j in ppp:
        if flag:
            if i not in A and i not in B:
                continue
            if j not in A and j not in B:
                continue
        if s[i] == s[j]:
            ok[s[i]].add(i)
            ok[s[j]].add(j)
        else:
            rok[s[i]].add(i)
            rok[s[j]].add(j)
        temp_ppp.add((i, j))

    if flag:
        tmplA = tta
        tmplB = ttb
    A = ok['A'] & rok['A'] 
    B = ok['B'] & rok['B'] 
    ppp = deepcopy(temp_ppp)
    flag = True

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(i) for i in input().split(' ')]
import sys
from collections import defaultdict
from copy import deepcopy

s = input().strip()
ppp = list()
for ll in sys.stdin:
    i, j = ll.strip().split(' ')
    i, j = int(i)-1, int(j)-1
    ppp.append((i, j))
A = None
B = None
tmplA = None
tmplB = None
flag = False

while True:
    if flag:
        if len(A) == 0 or len(B) == 0:
            break
        if tmplA != None:
            if tmplA == len(A) and tmplB == len(B):
                break

    ok = dict()
    ok['A'] = set()
    ok['B'] = set()
    rok = dict()
    rok['A'] = set()
    rok['B'] = set()
    for i, j in ppp:
        if flag:
            if i not in A and i not in B:
                continue
            if j not in A and j not in B:
                continue
        if s[i] == s[j]:
            ok[s[i]].add(i)
            ok[s[j]].add(j)
        else:
            rok[s[i]].add(i)
            rok[s[j]].add(j)

    if flag:
        tmplA = len(A)
        tmplB = len(B)
    A = ok['A'] & rok['A'] 
    B = ok['B'] & rok['B'] 
    flag = True

if len(A) == 0 or len(B) == 0:
    print('No')
else:
    print('Yes')

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
s = input()
edge = []
for i in range(m):
    a, b = map(int, input().split())
    edge.append((a, b))

node = list(range(1, n+1))
len_node_old = -1000
while True:
    for i in node:
        flg_a = flg_b = False
        include = []
        for a, b in edge:
            if a == i:
                if s[b-1] == 'A':
                    flg_a = True
                elif s[b-1] == 'B':
                    flg_b = True
                include.append((a, b))

            elif b == i:
                if s[a-1] == 'A':
                    flg_a = True
                elif s[a-1] == 'B':
                    flg_b = True
                include.append((a, b))

        if not (flg_a and flg_b):
            node.remove(i)
            for e in include:
                edge.remove(e)

    len_node = len(node)
    if len_node == 0:
        print('No')
        break
    if len_node_old - len_node == 0:
        print('Yes')
        break

    len_node_old = len_node

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
s = list(input())

S = []
for i in s: #S[i]=0なら頂点iのラベルは"A"、S[i]=1なら頂点iのラベルは"B"
    if i == "A": S.append(0)
    else: S.append(1)

#R[i]には頂点iと辺でつながっている頂点を入れる
R = [list() for _ in range(N)]
#C[i][0]には頂点iと辺でつながっているラベル"A"の数
#C[i][1]には頂点iと辺でつながっているラベル"B"の数
C = [[0, 0] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    R[a-1].append(b-1)
    R[b-1].append(a-1)
    C[a-1][S[b-1]] += 1
    C[b-1][S[a-1]] += 1

O = [0] * N #ダメな頂点には1を入れる
q = deque() #調べる頂点の候補リスト
for i in range(N):
    if C[i][0] * C[i][1] == 0: #もし少なくとも"A","B"どちらかに行けないなら
        q.append(i)
        O[i] = 1

while q:
    x = q.popleft()
    for v in R[x]:
        C[v][S[x]] -= 1
        if C[v][S[x]] == 0 and O[v] == 0:
            O[v] = 1
            q.append(v)

if sum(O) == N:
    answer = "No"
else:
    answer = "Yes"

print(answer)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())

sl = list(input())
abl = [list(map(int,input().split())) for _ in range(m)]


from collections import defaultdict
dic = defaultdict(list)

in_edge = [[0, 0] for i in range(n)]
for a, b in abl:
    dic[a-1].append(b-1)
    dic[b-1].append(a-1)
    if sl[b-1] == "A":
        in_edge[a-1][0] += 1
    else:
        in_edge[a - 1][1] += 1
    if a != b:
        if sl[a-1] == "A":
            in_edge[b - 1][0] += 1
        else:
            in_edge[b - 1][1] += 1

used = [0 for i in range(n)]
removes = []
for idx, (a,b) in enumerate(in_edge):
    if a == 0 or b == 0:
        removes.append(idx)
        used[idx] = 1

ans = 0
while removes:
    ans += 1
    v = removes.pop()
    for w in dic[v]:
        if v != w:
            if sl[v] == "A":
                in_edge[w][0] -= 1
                if in_edge[w][0] == 0 and used[w] == 0:
                    removes.append(w)
                    used[w] = 1
            else:
                in_edge[w][1] -= 1
                if in_edge[w][1] == 0 and used[w] == 0:
                    removes.append(w)
                    used[w] = 1

if ans == n:
    print("No")
else:
    print("Yes")

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    s = input()
    way = [[] for _ in range(n)]
    nway = [[0,0] for i in range(n)]
    for _ in range(m):
        a,b = map(int,ipt().split())
        a -= 1
        b -= 1
        way[a].append(b)
        way[b].append(a)
        if s[a] == "A":
            nway[b][0] += 1
        else:
            nway[b][1] += 1
        if s[b] == "A":
            nway[a][0] += 1
        else:
            nway[a][1] += 1
    al = [0]*n

    q = deque()
    for i,wi in enumerate(nway):
        if wi[0] == 0 or wi[1] == 0:
            q.append(i)

    while q:
        qi = q.pop()
        al[qi] = -1
        if s[qi] == "A":
            x = 0
        else:
            x = 1
        for i in way[qi]:
            if al[i] == 0:
                if nway[i][x] == 1:
                    q.append(i)
                else:
                    nway[i][x] -= 1

    if 0 in al:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

n, m = nm()
s = list(map(lambda x: ord(x) - ord('A'), list(ns())))
G = [list() for _ in range(n)]
w = [[0, 0] for _ in range(n)]
for _ in range(m):
  u, v = nm()
  u -= 1; v -= 1
  G[u].append(v)
  G[v].append(u)
  w[u][s[v]] += 1
  w[v][s[u]] += 1

dele = [0]*n
q = deque()
for v in range(n):
  if not w[v][0] * w[v][1]:
    q.append(v)
    dele[v] = 1
while q:
  v = q.popleft()
  for x in G[v]:
    w[x][s[v]] -= 1
    if w[x][s[v]] == 0 and not dele[x]:
      dele[x] = 1
      q.append(x)
print('Yes' if sum(dele) < n else 'No')

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

def main():
    N,M=map(int,input().split())
    s=input()
    dic={"A":[0 for i in range(N)],"B":[0 for i in range(N)]}
    edge=[[] for i in range(N)]

    for i in range(M):
        a,b=map(int,input().split())
        a-=1;b-=1
        edge[a].append(b)
        edge[b].append(a)
        dic[s[a]][b]+=1
        dic[s[b]][a]+=1

    que=set([])
    check=0
    for i in range(N):
        if dic["A"][i]==0 or dic["B"][i]==0:
            que.add(i)
            dic["A"][i]=float("inf")
            dic["B"][i]=float("inf")

    while que:
        v=que.pop()
        check+=v+1
        for nv in edge[v]:
            dic[s[v]][nv]-=1
            if dic["A"][nv]==0 or dic["B"][nv]==0:
                dic["A"][nv]=float("inf")
                dic["B"][nv]=float("inf")
                que.add(nv)

    if check==N*(N+1)//2:
        print("No")
    else:
        print("Yes")

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

def main():
    N,M=map(int,input().split())
    s=input()
    dic={"A":[0 for i in range(N)],"B":[0 for i in range(N)]}
    edge=[[] for i in range(N)]

    for i in range(M):
        a,b=map(int,input().split())
        a-=1;b-=1
        edge[a].append(b)
        edge[b].append(a)
        dic[s[a]][b]+=1
        dic[s[b]][a]+=1

    que=set([])
    check=0
    for i in range(N):
        if dic["A"][i]==0 or dic["B"][i]==0:
            que.add(i)


    while que:
        v=que.pop()
        check+=v+1
        dic["A"][v]=float("inf")
        dic["B"][v]=float("inf")
        for nv in edge[v]:
            dic[s[v]][nv]-=1
            if dic["A"][nv]==0 or dic["B"][nv]==0:
                que.add(nv)

    if check==N*(N+1)//2:
        print("No")
    else:
        print("Yes")

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N, M = map(int, input().split())
s = input()[:-1]
G = [[] for _ in range(N)]
A = [0]*N
B = [0]*N

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

q = deque([])
removed = [False]*N

for v in range(N):
    for nv in G[v]:
        if s[nv]=='A':
            A[v] += 1
        else:
            B[v] += 1
    
    if A[v]==0 or B[v]==0:
        q.append(v)
        removed[v] = True

while q:
    v = q.popleft()
    
    for nv in G[v]:
        if removed[nv]:
            continue
        
        if s[v]=='A':
            A[nv] -= 1
        else:
            B[nv] -= 1
        
        if A[nv]==0 or B[nv]==0:
            q.append(nv)
            removed[nv] = True

if False in removed:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, m = map(int, input().split())
s = input()

g = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

count = [[0, 0] for _ in range(n)]
bad = []

for i in range(n):
    for v in g[i]:
        if s[v] == 'A':
            count[i][0] += 1
        else:
            count[i][1] += 1
    if count[i][0]*count[i][1] == 0:
        bad.append(i)


visited = [False]*n
while bad:
    v = bad.pop()
    if visited[v]:
        continue
    visited[v] = True
    for w in g[v]:
        if not visited[w]:
            if s[v] == 'A':
                count[w][0] -= 1
            else:
                count[w][1] -= 1
            if count[w][0]*count[w][1] == 0:
                bad.append(w)

for i in range(n):
    if count[i][0]*count[i][1] > 0:
        print('Yes')
        exit()

print('No')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = input()

g = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

count = [[0, 0] for _ in range(n)]
bad = []

for i in range(n):
    for v in g[i]:
        if s[v] == 'A':
            count[i][0] += 1
        else:
            count[i][1] += 1
    if count[i][0]*count[i][1] == 0:
        bad.append(i)


visited = [False]*n
while bad:
    v = bad.pop()
    if visited[v]:
        continue
    visited[v] = True
    for w in g[v]:
        if not visited[w]:
            if s[v] == 'A':
                count[w][0] -= 1
            else:
                count[w][1] -= 1
            if count[w][0]*count[w][1] == 0:
                bad.append(w)

for i in range(n):
    if count[i][0]*count[i][1] > 0:
        print('Yes')
        exit()

print('No')

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    S = [i == "B" for i in input()]
    ab = [list(map(int, input().split())) for _ in [0]*M]
    graph = [set() for _ in [0]*N]
    [graph[a-1].add(b-1) for a, b in ab]
    [graph[b-1].add(a-1) for a, b in ab]

    status = [[0, 0] for _ in [0]*N]

    for i in range(N):
        for j in graph[i]:
            status[i][S[j]] += 1

    que = []
    for i, (p, q) in enumerate(status):
        if (p == 0) ^ (q == 0):
            que.append(i)

    while que:
        i = que.pop()
        c = S[i]
        for j in graph[i]:
            if i != j:
                graph[j].remove(i)
            status[j][c] -= 1
            p, q = status[j]
            if (p == 0) ^ (q == 0):
                que.append(j)
        graph[i] = set()

    for i in graph:
        if i:
            print("Yes")
            return
    print("No")


main()

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    n, m = map(int, input().split())
    s = [i == "B" for i in input()]
    ab = [list(map(int, input().split())) for _ in [0]*m]
    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]

    g2 = [[0, 0] for _ in [0]*n]

    for i in range(n):
        for j in g[i]:
            g2[i][s[j]] += 1

    ss = []
    for i, (j, k) in enumerate(g2):
        if (j == 0 and k > 0) or (j > 0 and k == 0):
            ss.append(i)

    while ss:
        i = ss.pop()
        c = s[i]
        for j in g[i]:
            if i != j:
                g[j].remove(i)
            g2[j][c] -= 1
            p, q = g2[j]
            if (p == 0) ^ (q == 0):
                ss.append(j)
        g[i] = set()

    for i in g:
        if len(i) > 0:
            print("Yes")
            return
    print("No")


main()