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: Wrong Answer

Solution code:
n, m = map(int, input().split())
s = [str(x) for x in input()]
a = []
b = []
for _ in range(m):
	l, r = map(int, input().split())
	b.append([l, r])
	a.append(s[l-1]+s[r-1])
ans = 'No'
if 'AA' in a and 'AB' in a and 'BB' in a:
	i, j, k = a.index('AA'), a.index('BB'), a.index('AB')
	if b[i][1] in [b[j][0],b[k][0]]:
		if b[j][1] == b[k][0] or b[k][1] == b[j][0]:
			ans = 'Yes'
	if b[j][1] in [b[i][0],b[k][0]]:
		if b[i][1] == b[k][0] or b[k][1] == b[i][0]:
			ans = 'Yes'
	if b[k][1] in [b[j][0],b[i][0]]:
		if b[j][1] == b[i][0] or b[i][1] == b[j][0]:
			ans = 'Yes'
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
s = input().rstrip()
G = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].add(b)
    G[b].add(a)
v = set(range(N))
while v:
    nv = set()
    for i in v:
        a = b = False
        ns = set()
        for j in G[i]:
            if j not in v:
                continue
            if s[j] == 'A':
                a = True
            else:
                b = True
            ns.add(j)
        if a and b:
            nv.add(i)
            G[i] = ns
    if len(v) == len(nv):
        print('Yes')
        exit()
    v = nv
print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
s = input().rstrip()
G = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].add(b)
    G[b].add(a)
v = set(range(N))
while v:
    nv = set()
    for i in v:
        a = b = False
        for j in G[i]:
            if j not in v:
                continue
            if s[j] == 'A':
                a = True
            else:
                b = True
        if a and b:
            nv.add(i)
    if len(v) == len(nv):
        print('Yes')
        exit()
    v = nv
print('No')

Submission status: Time Limit Exceeded

Solution code:
#####segfunc#####
def segfunc(x, y):
    if x[0]==0:
        return x
    else:
        return y
#################

#####ide_ele#####
ide_ele = [float("inf"),-1]
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k][0] += x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

import sys

input=sys.stdin.readline

def main():
    N,M=map(int,input().split())
    s=input()
    dic={"A":[[0,i] for i in range(N)],"B":[[0,i] 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][0]+=1
        dic[s[b]][a][0]+=1

    dic={moji:SegTree(dic[moji],segfunc,ide_ele) for moji in dic}

    ban=set([])
    while True:
        a,index=dic["A"].query(0,N)
        b,index2=dic["B"].query(0,N)
        if a==0:
            ban.add(index)
            dic["A"].update(index,float("inf"))
            dic["B"].update(index,float("inf"))
            for v in edge[index]:
                dic[s[index]].update(v,-1)

        elif b==0:
            ban.add(index2)
            dic["A"].update(index2,float("inf"))
            dic["B"].update(index2,float("inf"))
            for v in edge[index2]:
                dic[s[index2]].update(v,-1)
        else:
            break

    check=set([i for i in range(N)])
    if ban==check:
        print("No")
    else:
        print("Yes")

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#####segfunc#####
def segfunc(x, y):
    if x[0]>y[0]:
        return y
    elif x[0]<y[0]:
        return x
    elif x[1]>y[1]:
        return y
    else:
        return x
#################

#####ide_ele#####
ide_ele = [float("inf"),-1]
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k][0] += x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

import sys

input=sys.stdin.readline

def main():
    N,M=map(int,input().split())
    s=input()
    dic={"A":[[0,i] for i in range(N)],"B":[[0,i] 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][0]+=1
        dic[s[b]][a][0]+=1

    dic={moji:SegTree(dic[moji],segfunc,ide_ele) for moji in dic}

    ban=set([])
    while True:
        a,index=dic["A"].query(0,N)
        b,index2=dic["B"].query(0,N)
        if a==0:
            ban.add(index)
            dic["A"].update(index,float("inf"))
            dic["B"].update(index,float("inf"))
            for v in edge[index]:
                dic[s[index]].update(v,-1)

        elif b==0:
            ban.add(index2)
            dic["A"].update(index2,float("inf"))
            dic["B"].update(index2,float("inf"))
            for v in edge[index2]:
                dic[s[index2]].update(v,-1)
        else:
            break

    check=set([i for i in range(N)])
    if ban==check:
        print("No")
    else:
        print("Yes")

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#####segfunc#####
def segfunc(x, y):
    if x[0]>y[0]:
        return y
    elif x[0]<y[0]:
        return x
    elif x[1]>y[1]:
        return y
    else:
        return x
#################

#####ide_ele#####
ide_ele = [float("inf"),-1]
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k][0] += x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

import sys

input=sys.stdin.readline

N,M=map(int,input().split())
s=input()
dic={"A":[[0,i] for i in range(N)],"B":[[0,i] 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][0]+=1
    dic[s[b]][a][0]+=1

dic={moji:SegTree(dic[moji],segfunc,ide_ele) for moji in dic}

ban=set([])
while True:
    a,index=dic["A"].query(0,N)
    b,index2=dic["B"].query(0,N)
    if a==0:
        ban.add(index)
        dic["A"].update(index,float("inf"))
        dic["B"].update(index,float("inf"))
        for v in edge[index]:
            dic[s[index]].update(v,-1)

    elif b==0:
        ban.add(index2)
        dic["A"].update(index2,float("inf"))
        dic["B"].update(index2,float("inf"))
        for v in edge[index2]:
            dic[s[index2]].update(v,-1)
    else:
        break

check=set([i for i in range(N)])
if ban==check:
    print("No")
else:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
#####segfunc#####
def segfunc(x, y):
    return min(x,y)
#################

#####ide_ele#####
ide_ele = [float("inf"),-1]
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k][0] += x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

import sys

input=sys.stdin.readline

N,M=map(int,input().split())
s=input()
A=[[0,i] for i in range(N)]
B=[[0,i] 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)
    A[b][0]+=(s[a]=="A")
    B[b][0]+=(s[a]=="B")
    A[a][0]+=(s[b]=="A")
    B[a][0]+=(s[b]=="B")

Acheck=SegTree(A,segfunc,ide_ele)
Bcheck=SegTree(B,segfunc,ide_ele)

ban=set([])
while True:
    a,index=Acheck.query(0,N)
    b,index2=Bcheck.query(0,N)
    if a==0:
        ban.add(index)
        Acheck.update(index,float("inf"))
        Bcheck.update(index,float("inf"))
        if s[index]=="A":
            for v in edge[index]:
                Acheck.update(v,-1)
        else:
            for v in edge[index]:
                Bcheck.update(v,-1)
    elif b==0:
        ban.add(index2)
        Acheck.update(index2,float("inf"))
        Bcheck.update(index2,float("inf"))
        if s[index2]=="A":
            for v in edge[index2]:
                Acheck.update(v,-1)
        else:
            for v in edge[index2]:
                Bcheck.update(v,-1)
    else:
        break

check=set([i for i in range(N)])
if ban==check:
    print("No")
else:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
#####segfunc#####
def segfunc(x, y):
    if x[0]>y[0]:
        return y
    elif x[0]<y[0]:
        return x
    elif x[1]>y[1]:
        return y
    else:
        return x
#################

#####ide_ele#####
ide_ele = (float("inf"),-1)
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k][0] += x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

import sys

input=sys.stdin.readline

N,M=map(int,input().split())
s=input()
A=[[0,i] for i in range(N)]
B=[[0,i] 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)
    if s[a]=="A":
        A[b][0]+=1
    else:
        B[b][0]+=1
    if s[b]=="A":
        A[a][0]+=1
    else:
        B[a][0]+=1

Acheck=SegTree(A,segfunc,ide_ele)
Bcheck=SegTree(B,segfunc,ide_ele)

ban=set([])
while True:
    a,index=Acheck.query(0,N)
    b,index2=Bcheck.query(0,N)
    if a==0:
        ban.add(index)
        Acheck.update(index,float("inf"))
        Bcheck.update(index,float("inf"))
        for v in edge[index]:
            if s[index]=="A":
                Acheck.update(v,-1)
            else:
                Bcheck.update(v,-1)
    elif b==0:
        ban.add(index2)
        Acheck.update(index2,float("inf"))
        Bcheck.update(index2,float("inf"))
        for v in edge[index2]:
            if s[index2]=="A":
                Acheck.update(v,-1)
            else:
                Bcheck.update(v,-1)
    else:
        break

check=set([i for i in range(N)])
if ban==check:
    print("No")
else:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input=stdin.readline
    from copy import deepcopy
    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 deepcopy(g[i]):
            g[j].remove(i)
            g2[j][c] -= 1
            p, q = g2[j]
            if (p == 0 and q > 0) or (p > 0 and q == 0):
                ss.append(j)
        g[i] = set()

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


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from copy import deepcopy
    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 deepcopy(g[i]):
            g[j].remove(i)
            g2[j][c] -= 1
            p, q = g2[j]
            if (p == 0 and q > 0) or (p > 0 and q == 0):
                ss.append(j)
        g[i] = set()

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


main()

Submission status: Time Limit Exceeded

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

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


checked = set()

path = set()

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

for item in ds[0].keys():
    if item not in checked:
        path.add(item)
        if walk(item, 0):
            print('Yes')
            break
        path.remove(item)
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import heapq
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M = list(map(int, sys.stdin.buffer.readline().split()))
S = sys.stdin.buffer.readline().decode().rstrip()
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

graph = [defaultdict(int) for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a][b] += 1
    if a != b:
        graph[b][a] += 1

# AB 両方と隣接する頂点のみで部分グラフを作れるか
# どっちかとしか隣接しない頂点を取り除いていく
# removed = True
# while removed:
#     removed = False
#     for v in range(N):
#         if not graph[v]:
#             continue
#         a = 0
#         b = 0
#         for u in graph[v]:
#             if S[u] == 'A':
#                 a += 1
#             else:
#                 b += 1
#         if a == 0 or b == 0:
#             for u in graph[v]:
#                 graph[u].remove(v)
#             graph[v] = []
#             removed = True
# print(graph)


a_counts = [[0, v] for v in range(N)]
b_counts = [[0, v] for v in range(N)]
for v in range(N):
    for u, cnt in graph[v].items():
        if S[u] == 'A':
            a_counts[v][0] += cnt
        else:
            b_counts[v][0] += cnt
# shallow copy
a_heap = a_counts[:]
b_heap = b_counts[:]

cont = True
while cont:
    cont = False
    heapq.heapify(a_heap)
    heapq.heapify(b_heap)
    while a_heap and a_heap[0][0] == 0:
        _, v = heapq.heappop(a_heap)
        for u, cnt in list(graph[v].items()):
            if S[v] == 'A':
                a_counts[u][0] -= cnt
            else:
                b_counts[u][0] -= cnt
            del graph[u][v]
        graph[v] = {}
        cont = True
    while b_heap and b_heap[0][0] == 0:
        _, v = heapq.heappop(b_heap)
        for u, cnt in list(graph[v].items()):
            if S[v] == 'A':
                a_counts[u][0] -= cnt
            else:
                b_counts[u][0] -= cnt
            del graph[u][v]
        graph[v] = {}
        cont = True

ok = any(graph)
if ok:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import heapq
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M = list(map(int, sys.stdin.buffer.readline().split()))
S = sys.stdin.buffer.readline().decode().rstrip()
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

graph = [defaultdict(int) for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a][b] += 1
    if a != b:
        graph[b][a] += 1

# AB 両方と隣接する頂点のみで部分グラフを作れるか
# どっちかとしか隣接しない頂点を取り除いていく
# removed = True
# while removed:
#     removed = False
#     for v in range(N):
#         if not graph[v]:
#             continue
#         a = 0
#         b = 0
#         for u in graph[v]:
#             if S[u] == 'A':
#                 a += 1
#             else:
#                 b += 1
#         if a == 0 or b == 0:
#             for u in graph[v]:
#                 graph[u].remove(v)
#             graph[v] = []
#             removed = True
# print(graph)


a_counts = [[0, v] for v in range(N)]
b_counts = [[0, v] for v in range(N)]
for v in range(N):
    for u, cnt in graph[v].items():
        if S[u] == 'A':
            a_counts[v][0] += cnt
        else:
            b_counts[v][0] += cnt
# shallow copy
a_heap = a_counts.copy()
b_heap = b_counts.copy()

cont = True
while cont:
    cont = False
    heapq.heapify(a_heap)
    heapq.heapify(b_heap)
    while a_heap and a_heap[0][0] == 0:
        _, v = heapq.heappop(a_heap)
        for u, cnt in list(graph[v].items()):
            if S[v] == 'A':
                a_counts[u][0] -= cnt
            else:
                b_counts[u][0] -= cnt
            del graph[u][v]
        graph[v] = {}
        cont = True
    while b_heap and b_heap[0][0] == 0:
        _, v = heapq.heappop(b_heap)
        for u, cnt in list(graph[v].items()):
            if S[v] == 'A':
                a_counts[u][0] -= cnt
            else:
                b_counts[u][0] -= cnt
            del graph[u][v]
        graph[v] = {}
        cont = True

ok = any(graph)
if ok:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

import heapq

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M = list(map(int, sys.stdin.buffer.readline().split()))
S = sys.stdin.buffer.readline().decode().rstrip()
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

graph = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append(b)
    if a != b:
        graph[b].append(a)

# AB 両方と隣接する頂点のみで部分グラフを作れるか
# どっちかとしか隣接しない頂点を取り除いていく
# removed = True
# while removed:
#     removed = False
#     for v in range(N):
#         if not graph[v]:
#             continue
#         a = 0
#         b = 0
#         for u in graph[v]:
#             if S[u] == 'A':
#                 a += 1
#             else:
#                 b += 1
#         if a == 0 or b == 0:
#             for u in graph[v]:
#                 graph[u].remove(v)
#             graph[v] = []
#             removed = True
# print(graph)


a_counts = [[0, v] for v in range(N)]
b_counts = [[0, v] for v in range(N)]
for v in range(N):
    for u in graph[v]:
        if S[u] == 'A':
            a_counts[v][0] += 1
        else:
            b_counts[v][0] += 1
# shallow copy
a_heap = a_counts.copy()
b_heap = b_counts.copy()

removed = [False] * N
cont = True
while cont:
    cont = False
    heapq.heapify(a_heap)
    heapq.heapify(b_heap)
    while a_heap and a_heap[0][0] == 0:
        _, v = heapq.heappop(a_heap)
        for u in graph[v]:
            if removed[u]:
                continue
            if S[v] == 'A':
                a_counts[u][0] -= 1
            else:
                b_counts[u][0] -= 1
        cont = True
        removed[v] = True
    while b_heap and b_heap[0][0] == 0:
        _, v = heapq.heappop(b_heap)
        for u in graph[v]:
            if removed[u]:
                continue
            if S[v] == 'A':
                a_counts[u][0] -= 1
            else:
                b_counts[u][0] -= 1
        cont = True
        removed[v] = True

ok = not all(removed)
if ok:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M = list(map(int, sys.stdin.buffer.readline().split()))
S = sys.stdin.buffer.readline().decode().rstrip()
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

graph = [set() for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].add(b)
    graph[b].add(a)


# @debug
def dfs(v, pc=None, seen=None):
    seen = seen or set()

    if v in seen:
        return True
    seen.add(v)

    if pc is None or pc == S[v]:
        ok = False
        for u in graph[v]:
            if S[u] != S[v]:
                if dfs(u, S[v], seen):
                    ok = True
                    break
        if not ok:
            seen.remove(v)
            return False

    if pc is None or pc != S[v]:
        ok = False
        for u in graph[v]:
            if S[u] == S[v]:
                if dfs(u, S[v], seen):
                    ok = True
                    break
        if not ok:
            seen.remove(v)
            return False
    return True


ok = False
for v in range(N):
    if dfs(v):
        ok = True
        break
if ok:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M = list(map(int, sys.stdin.buffer.readline().split()))
S = sys.stdin.buffer.readline().decode().rstrip()
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

graph = [set() for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].add(b)
    graph[b].add(a)



# @debug
def dfs(v, pc=None, seen=None):
    seen = seen or set()

    if v in seen:
        return True
    seen.add(v)

    if pc is None or pc == S[v]:
        ok = False
        for u in graph[v]:
            if S[u] != S[v]:
                ok |= dfs(u, S[v], seen)
        if not ok:
            seen.remove(v)
            return False

    if pc is None or pc != S[v]:
        ok = False
        for u in graph[v]:
            if S[u] == S[v]:
                ok |= dfs(u, S[v], seen)
        if not ok:
            seen.remove(v)
            return False
    return True


ok = False
for v in range(N):
    ok |= dfs(v)
if ok:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
s = list(input())
connect = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    connect[a-1].add(b-1)
    connect[b-1].add(a-1)
def check(xs):
    a, b = 0, 0
    for x in xs:
        if s[x] == 'A':
            a = 1
        elif s[x] == 'B':
            b = 1
        if a & b:
            return True
    return False
update = True
while update:
    update = False
    for i in range(n):
        if s[i] != 'X':
            if not check(connect[i]):
                update = True
                s[i] = 'X'
if 'A' in s and 'B' in s: print('Yes')
else: print('No')