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: 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 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: Accepted

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
S = ["?"] + list(input())[: -1]
e = dd(set)
a = [0] * (N + 1)
b = [0] * (N + 1)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].add(v)
  e[v].add(u)

s = []
for x in range(1, N + 1):
  for y in e[x]:
    if S[y] == "A": a[x] += 1
    if S[y] == "B": b[x] += 1
  if a[x] == 0 or (b[x] == 0): s.append(x)

vis = [0] * (N + 1)
while len(s):
  x = s.pop()
  if vis[x]: continue
  vis[x] = 1
  for y in e[x]:
    if x == y: continue
    if S[x] == "A": a[y] -= 1
    if S[x] == "B": b[y] -= 1
    if a[y] == 0 or (b[y] == 0): s.append(y)
 
if sum(vis) < N: print("Yes")
else: print("No")

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
def check(E):
    L = []
    n = len(E)
    done = [0] * n
    checking = [0] * n
    Q = []
    for i in range(n)[::-1]:
        Q.append(~i)
        Q.append(i)
    while Q:
        j = Q.pop()
        if j < 0:
            if done[~j]: continue
            done[~j] = 1
            L.append(~j)
            checking[~j] = 0
            continue
        if done[j]: continue
        checking[j] = 1
        for k in E[j]:
            if checking[k]:
                return 1
            Q.append(~k)
            Q.append(k)
    return 0

N, M = map(int, input().split())
S = [ord(a)-65 for a in input()]
X = [[] for _ in range(N*2)]

for _ in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    if S[a] == S[b]:
        X[a].append(b+N)
        X[b].append(a+N)
    else:
        X[a+N].append(b)
        X[b+N].append(a)

print("Yes" if check(X) else "No")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = input()
G = [[] for _ in range(n)]
A = [0]*n
B = [0]*n
for _ in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  if a==b:
    G[a].append(b)
    if s[b] == "A":
      A[a] += 1
    else:
      B[a] += 1
  else:
    G[a].append(b)
    G[b].append(a)
    if s[b] == "A":
      A[a] += 1
    else:
      B[a] += 1
    if s[a] == "A":
      A[b] += 1
    else:
      B[b] += 1
stack = []
cnt = 0
for i in range(n):
  if (not A[i]) or (not B[i]):
    stack.append(i)
while stack:
  v = stack.pop()
  cnt += 1
  if s[v] == "A":
    for nv in G[v]:
      A[nv] -= 1
      if B[nv] > 0 and A[nv] == 0:
        stack.append(nv)
  else:
    for nv in G[v]:
      B[nv] -= 1
      if A[nv] > 0 and B[nv] == 0:
        stack.append(nv)
if cnt == n:
  print("No")
else:
  print("Yes")

Submission status: Accepted

Solution code:
from collections import deque


n, m = map(int, input().split())
s = input()
info = [list(map(int, input().split())) for i in range(m)]

graph = [[] for i in range(n)]
for i in range(m):
    a, b = info[i]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

v_num = [0] * n 
for i in range(n):
    if s[i] == "B":
        v_num[i] = 1

q = deque([])
used = [False] * n
v_cnt = [[0, 0] for i in range(n)]
for i in range(n):
    for j in graph[i]:
        v_cnt[j][v_num[i]] += 1
for i in range(n):
    if v_cnt[i][0] * v_cnt[i][1] == 0:
        q.append(i)
        used[i] = True

while q:
    pos = q.pop()
    for next_pos in graph[pos]:
        if used[next_pos]:
            continue
        v_cnt[next_pos][v_num[pos]] -= 1
        if v_cnt[next_pos][v_num[pos]] == 0:
            q.append(next_pos)
            used[next_pos] = True

for i in range(n):
    if not used[i]:
        print("Yes")
        exit()
print("No")

Submission status: Accepted

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

n,m = map(int,input().split())
s = input()
ab = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
ABs = [[0,0] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  if s[a-1] == "A":
    ABs[b][0] += 1
  else:
    ABs[b][1] += 1
  if s[b-1] == "A":
    ABs[a][0] += 1
  else:
    ABs[a][1] += 1
ablack = [-1 for i in range(n+1)]
ablack[0] = 0
stack = []
visited = [0 for i in range(n+1)]
for x in range(1,n+1):
  if ABs[x][0] == 0 or ABs[x][1] == 0:
    if s[x-1] == "A":
      ablack[x] = 0
    else:
      ablack[x] = 1
    stack.append(x)

while stack:
  x = stack.pop()
  if visited[x] == 1:
    continue
  visited[x] = 1
  for y in graph[x]:
    if visited[y] == 0:
      if ablack[x] == 0:
        ABs[y][0] -= 1
      else:
        ABs[y][1] -= 1
      if ABs[y][0] <= 0 or ABs[y][1] <= 0:
        if s[y-1] == "A":
          ablack[y] = 0
        else:
          ablack[y] = 1
        stack.append(y)
if ablack.count(-1) >= 1:
  print("Yes")
else:
  print("No")

Submission status: Accepted

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

N, M = map(int, input().split())
S = input().rstrip()
AB = []
AA = []
BB = []
for _ in range(M):
    a, b = map(int, input().split())
    if S[a-1] == "A" and S[b-1] == "B":
        AB.append((a-1, b-1))
    elif S[a-1] == "B" and S[b-1] == "A":
        AB.append((b-1, a-1))
    elif S[a-1] == "A":
        AA.append((a-1, b-1))
    else:
        BB.append((a-1, b-1))

graph = [set() for _ in range(2*N)]
to_A = [False]*N
to_B = [False]*N

for a, b in AB:
    graph[a].add(b)
    graph[b+N].add(a+N)
    to_B[a] = True
    to_A[b] = True

for a, b in AA:
    if to_B[a] or to_B[b]:
        graph[b+N].add(a)
        graph[a+N].add(b)

for a, b in BB:
    if to_A[a] or to_A[b]:
        graph[a].add(b+N)
        graph[b].add(a+N)


Color = [-1]*(2*N)
loop = False

for n in range(2*N):
    if Color[n] != -1:
        continue
    stack = [n]
    Color[n] = n
    while stack:
        p = stack[-1]
        update = False
        for np in graph[p]:
            if Color[np] == -1:
                update = True
                Color[np] = n
                stack.append(np)
                break
            elif len(stack) > 1:
                if np != stack[-2] and Color[np] == n:
                    loop = True
                    break
        if not update:
            stack.pop()
            Color[p] = 10**14
        if loop:
            break
    if loop:
        break

print("Yes" if loop else "No")

Submission status: Accepted

Solution code:
import sys
from collections import deque
readline = sys.stdin.readline
N, M = map(int, readline().split())
Col = [1 if s == 'A' else 0 for s in readline().strip()]

Edge = [[] for _ in range(N)]
Dim = [[0, 0] for _ in range(N)]
for _ in range(M):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)
    Dim[a][Col[b]] += 1
    Dim[b][Col[a]] += 1

Q = deque([i for i in range(N) if not min(Dim[i])])
used = set(Q)

while Q:
    vn = Q.pop()
    c = Col[vn]
    for vf in Edge[vn]:
        if vf in used:
            continue
        Dim[vf][c] -= 1
        if not Dim[vf][c]:
            used.add(vf)
            Q.appendleft(vf)

print('Yes' if len(used) < N else 'No')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))


def main():
    n, m = map(int, input().split())
    s = input().strip()
    ab = [tuple(map(int, input().split())) for _ in range(m)]
    edges = [[] for _ in range(n)]
    for a, b in ab:
        edges[a - 1].append(b - 1)
        edges[b - 1].append(a - 1)
    
    ab = [[0, 0] for i in range(n)]
    stack = []
    for i in range(n):
        for e in edges[i]:
            if s[e] == 'A':
                ab[i][0] += 1
            else:
                ab[i][1] += 1
        if ab[i][0] == 0 or ab[i][1] == 0:
            stack.append(i)
    
    deleted = [False for i in range(n)]
    while len(stack) > 0:
        q = stack.pop()
        if deleted[q]:
            continue
        deleted[q] = True
        for e in edges[q]:
            if not deleted[e]:
                if s[q] == 'A':
                    ab[e][0] -= 1
                    if ab[e][0] == 0:
                        stack.append(e)
                else:
                    ab[e][1] -= 1
                    if ab[e][1] == 0:
                        stack.append(e)
    
    for d in deleted:
        if not d:
            print("Yes")
            break
    else:
        print("No")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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
candidates = []
for c, v in a_counts + b_counts:
    if c == 0:
        candidates.append(v)

while candidates:
    v = candidates.pop()
    if not graph[v]:
        continue
    for u, cnt in list(graph[v].items()):
        if S[v] == 'A':
            a_counts[u][0] -= cnt
            if a_counts[u][0] == 0:
                candidates.append(u)
        else:
            b_counts[u][0] -= cnt
            if b_counts[u][0] == 0:
                candidates.append(u)
        del graph[u][v]
    graph[v] = {}

# print(graph)

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

Submission status: Accepted

Solution code:
def examC():
    N,M = LI()
    S = SI()
    V = [[] for _ in range(N)]
    ok = [1]*N
    acnt = [0]*N; bcnt = [0]*N
    for _ in range(M):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
        if S[a-1]=="A":
            acnt[b-1] +=1
        else:
            bcnt[b-1] +=1
        if S[b-1]=="A":
            acnt[a-1] +=1
        else:
            bcnt[a-1] +=1
    NGque = deque()
    for i in range(N):
        if acnt[i]==0 or bcnt[i]==0:
            ok[i]=0
            NGque.append(i)
#    print(ok,acnt,bcnt)
#    print(NGque)
    while(NGque):
        cur = NGque.pop()
        for i in V[cur]:
            if ok[i]==1:
                if S[cur] == "A":
                    acnt[i] -= 1
                else:
                    bcnt[i] -= 1
                if acnt[i] == 0 or bcnt[i] == 0:
                    ok[i] = 0
                    NGque.append(i)
    if max(ok)==1:
        ans = "Yes"
    else:
        ans = "No"
    print(ans)

import sys,copy,bisect,itertools,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()

Submission status: Accepted

Solution code:
#ライブラリインポート
from collections import defaultdict, deque

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	#入力
	N, M = getlist()
	s = list(input())
	outE = defaultdict(list)
	inEA = defaultdict(int)
	inEB = defaultdict(int)
	E = set()
	for i in range(M):
		a, b = sorted(getlist())
		a = a - 1
		b = b - 1
		E.add((a, b))
	E = list(E)
	#print(E)
	m = len(E)
	for i in range(m):
		a = E[i][0]
		b = E[i][1]
		outE[a].append(b)
		outE[b].append(a)
		if s[a] == "A":
			inEA[b] += 1
		else:
			inEB[b] += 1

		if s[b] == "A":
			inEA[a] += 1
		else:
			inEB[a] += 1
	
	Q = deque()
	for i in range(N):
		if inEA[i] == 0 or inEB[i] == 0:
			Q.append(i)

	visit = ["No"] * N
	check = ["Yes"] * N
	while Q:
		u = Q.popleft()
		if visit[u] == "Yes":
			continue
		visit[u] = "Yes"
		check[u] = "No"
		for v in outE[u]:
			if s[u] == "A":
				inEA[v] -= 1
				if inEA[v] == 0:
					check[v] = "No"
					Q.append(v)
			else:
				inEB[v] -= 1
				if inEB[v] == 0:
					check[v] = "No"
					Q.append(v)

	judge = "No"
	#print(check)
	for i in range(N):
		if check[i] == "Yes":
			judge = "Yes"
	print(judge)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

N, M = map(int, input().split())
s = input()
label = [0] * (N+1)
for i in range(N):
    if s[i] == 'B':
        label[i+1] = 1
adj = [[] for _ in range(N+1)]
ab_num = [[0, 0] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)
    ab_num[a][label[b]] += 1
    ab_num[b][label[a]] += 1

stack = []
remain = [1] * (N+1)
for i in range(1, N+1):
    if ab_num[i][0] == 0 or ab_num[i][1] == 0:
        stack.append(i)
        remain[i] = 0

cnt = N - len(stack)
while stack:
    if cnt == 0:
        print('No')
        exit()
    v = stack.pop()
    for u in adj[v]:
        if remain[u]:
            if ab_num[u][label[v]] == 1:
                remain[u] = 0
                stack.append(u)
                cnt -= 1
            else:
                ab_num[u][label[v]] -= 1

print('Yes')

Submission status: Accepted

Solution code:
from collections import deque
import sys

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

s = input()

dic = {}
linkA = [0] * N
linkB = [0] * N
able = [True] * N

for i in range(M):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

    dic[a].append(b)
    dic[b].append(a)

    if s[a] == "A":
        linkA[b] += 1
    else:
        linkB[b] += 1

    if s[b] == "A":
        linkA[a] += 1
    else:
        linkB[a] += 1

#print (linkA,linkB)
q = deque([])

for i in range(N):

    if linkA[i] == 0 or linkB[i] == 0:
        able[i] = False
        q.append(i)

while len(q) > 0:

    now = q.popleft()
    #print (q)

    if now in dic:
        for i in dic[now]:

            if s[now] == "A":
                linkA[i] -= 1
            else:
                linkB[i] -= 1


            if (linkA[i] <= 0 or linkB[i] <= 0) and able[i]:
                able[i] = False
                q.append(i)

for i in able:
    if i:
        print ("Yes")
        sys.exit()

print ("No")

Submission status: Accepted

Solution code:
def scc(E, n_vertex):
    # 強連結成分分解  # E は [[a1, b1], [a2, b2], ... ] の形
    # 返り値は 強連結成分の数 と 各頂点がどの強連結成分に属しているか
    # numpy いらないのは https://tjkendev.github.io/procon-library/python/graph/scc.html
    import numpy as np
    from scipy.sparse import csr_matrix, csgraph
    A, B = np.array(E).T
    graph = csr_matrix((np.ones(len(E)), (A, B)), (n_vertex, n_vertex))
    n_components, labels = csgraph.connected_components(graph, connection='strong')
    return n_components, labels

N, M = map(int, input().split())
S = "_" + input()
E = []
for _ in range(M):
    a, b = map(int, input().split())
    if S[a]==S[b]:
        E.append([a, N+b])
        E.append([b, N+a])
    else:
        E.append([N+a, b])
        E.append([N+b, a])

n_components, _ = scc(E, 2*N+1)
if n_components == 2*N+1:
    print("No")
else:
    print("Yes")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
s = input()
C = [[0, 0] for _ in range(N)]
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    if s[b-1] == 'A':
        C[a-1][0]+=1
    else:
        C[a-1][1]+=1
    if s[a-1] == 'A':
        C[b-1][0]+=1
    else:
        C[b-1][1]+=1
    G[a-1].append(b-1)
    G[b-1].append(a-1)
que = []
deleted = [False]*N
for i in range(N):
    if C[i][0] == 0 or C[i][1] == 0:
        que.append(i)
        deleted[i] = True
while que:
    v = que.pop()
    if s[v] == 'A':
        i = 0
    else:
        i = 1
    for nv in G[v]:
        if deleted[nv]:
            continue
        C[nv][i]-=1
        if C[nv][i]==0:
            que.append(nv)
            deleted[nv] = True
if all(f for f in deleted):
    print('No')
else:
    print('Yes')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S="0"+input()
E=[[] for i in range(N+1)]
AOUT=[0]*(N+1)
BOUT=[0]*(N+1)

for i in range(M):
    x,y=map(int,input().split())
    E[x].append(y)
    E[y].append(x)

    if S[x]=="A":
        AOUT[y]+=1
    else:
        BOUT[y]+=1

    if S[y]=="A":
        AOUT[x]+=1
    else:
        BOUT[x]+=1

from collections import deque
Q=deque()

USE=[0]*(N+1)

for i in range(N+1):
    if AOUT[i]==0 or BOUT[i]==0:
        Q.append(i)
        USE[i]=1

while Q:
    x=Q.pop()

    for to in E[x]:
        if USE[to]==0:
            if S[x]=="A":
                AOUT[to]-=1
            else:
                BOUT[to]-=1

            if AOUT[to]==0 or BOUT[to]==0:
                Q.append(to)
                USE[to]=1

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

Submission status: Accepted

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

"""
AABBAABBAABB..が作れることと同値
"""

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

N,M = map(int,input().split())
S = input().rstrip()
# 0-indexedにしておく
AB = [[int(x)-1 for x in row.split()] for row in sys.stdin.readlines()]

# 頂点倍化しておく。同じ色から来る着地点、異なる色から来る着地点
edge = []
for a,b in AB:
    s = S[a]; t = S[b]
    if s == t:
        edge.append((a+N,b))
        if a != b:
            edge.append((b+N,a))
    else:
        edge.append((a,b+N))
        edge.append((b,a+N))

row,col = zip(*edge)

graph = csr_matrix(([1]*len(row),(row,col)),(2*N,2*N))

n_component,_ = connected_components(graph,connection='strong')

answer = 'Yes' if n_component < 2*N else 'No'
print(answer)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
n, m = map(int, input().split())
s = input()
out = [set() for _ in range(n)]
count = [[0, 0] for _ in range(n)]
def f(c):
    if c == 'A': return 0
    else: return 1
for _ in range(m):
    a, b = map(int, input().split())
    if a == b:
        count[a-1][f(s[a-1])] += 1
    elif b-1 not in out[a-1]:
        count[a-1][f(s[b-1])] += 1
        count[b-1][f(s[a-1])] += 1
    out[a-1].add(b-1)
    out[b-1].add(a-1)
elim = set()
def eliminate(x):
    elim.add(x)
    c = f(s[x])
    for node in out[x]:
        if node not in elim:
            count[node][c] -= 1
            if count[node][0] * count[node][1] == 0:
                eliminate(node)
for i in range(n):
    if i not in elim and count[i][0] * count[i][1] == 0:
        eliminate(i)
if len(elim) < n: print('Yes')
else: print('No')

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque
n,m=map(int,input().split())
s=input()
A=[0]*n
B=[0]*n
Edges=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    if a==b:
        if s[a]=='A':
            A[a]+=1
        else:
            B[a]+=1
    else:
        Edges[a].append(b)
        Edges[b].append(a)
        if s[a]=='A':
            A[b]+=1
        else:
            B[b]+=1
        if s[b]=='A':
            A[a]+=1
        else:
            B[a]+=1
Del=[False]*n
q=deque()
for i in range(n):
    if A[i]*B[i]==0:
        q.append(i)
        Del[i]=True
while q:
    u=q.pop()
    l=s[u]
    for v in Edges[u]:
        if Del[v]:
            continue
        if l=='A':
            A[v]-=1
        else:
            B[v]-=1
        if A[v]*B[v]==0:
            q.append(v)
            Del[v]=True
print('No' if sum(Del)==n else 'Yes')

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
s=input()
H=[[] for i in range(N)]
G=[[] for i in range(2*N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    H[a].append(b)
    H[b].append(a)
    if s[a]=="A":
        if s[b]=="A":
            G[a].append(N+b)
            G[b].append(N+a)
        else:
            G[a+N].append(b+N)
            G[b].append(a)
    else:
        if s[b]=="A":
            G[a].append(b)
            G[N+b].append(N+a)
        else:
            G[N+a].append(b)
            G[N+b].append(a)
K=[0 for i in range(2*N)]
for i in range(2*N):
    for p in G[i]:
        K[p]+=1
q=deque(i for i in range(2*N) if K[i]==0)
res=[]
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in G[v1]:
        K[v2]-=1
        if K[v2]==0:
            q.append(v2)
if len(res)==2*N:
    print("No")
else:
    print("Yes")

Submission status: Accepted

Solution code:
import sys
from collections import deque
N,M=map(int,input().split())
s=input()
table=[]
for i in range(M):
    x,y=map(int,input().split())
    table.append((x-1,y-1))
A=[0]*N
B=[0]*N
edge=[[] for i in range(N)]
S=[False]*N
L=deque()
for x,y in table:
    if x==y:
        #edge[x].append(y)
        if s[x]=='A':
            A[x]+=1
        else:
            B[x]+=1
        continue
    edge[x].append(y)
    edge[y].append(x)
    if s[x]=='A':
        A[y]+=1
    else:
        B[y]+=1
    if s[y]=='A':
        A[x]+=1
    else:
        B[x]+=1 
        
for i in range(N):
    if A[i]*B[i]==0:
        L.append(i)
        S[i]=True

while L:
    x=L.pop()
    t=s[x]
    for y in edge[x]:
        if S[y]:
            continue
        if t=='A':
            A[y]-=1
        else:
            B[y]-=1
        if A[y]*B[y]==0:
            L.append(y)
            S[y]=True
if sum(S)!=N:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
import sys
from collections import deque
N,M=map(int,input().split())
s=input()
table=[]
for i in range(M):
    x,y=map(int,input().split())
    table.append((x-1,y-1))
edge=[[]for i in range(2*N)]
visit=[0]*(2*N)
for x,y in table:
    if x==y:
        edge[2*x].append(2*x+1)
        visit[2*x+1]+=1
        continue
    if s[x]==s[y]:
        edge[2*x].append(2*y+1)
        edge[2*y].append(2*x+1)
        visit[2*x+1]+=1
        visit[2*y+1]+=1
        continue
    edge[2*x+1].append(2*y)
    edge[2*y+1].append(2*x)
    visit[2*x]+=1
    visit[2*y]+=1
S=set()
L=deque()

for i in range(2*N):
    if visit[i]==0:
        L.append(i)

while L:
    x=L.pop()
    S.add(x)
    for y in edge[x]:
        visit[y]-=1
        if visit[y]==0:
            L.append(y)
if len(S)!=2*N:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
S = input()

# 頂点iがラベルA・Bの頂点といくつ隣接しているか
connect_label = [[0, 0] for i in range(N)]

# 削除する予定の頂点を管理するキュー
queue = deque()

# 削除済みの頂点を管理する集合
deleted_set = set()

# 各頂点の連結情報
G = [[] for i in range(N)]

# 辺の情報を入力
for i in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    G[a].append(b)
    G[b].append(a)
    connect_label[a][1 - (S[b] == "A")] += 1
    connect_label[b][1 - (S[a] == "A")] += 1

# AまたはBのみとしか連結してないものをキューに追加
for i in range(N):
    if 0 in connect_label[i]:
        queue.append(i)

# キューが空になるまで削除を繰り返す
while queue:
    n = queue.pop()

    # すでに削除していれば何もしない
    if n in deleted_set:
        continue

    # 連結していた頂点について情報を書き換える
    for v in G[n]:
        connect_label[v][1 - (S[n] == "A")] -= 1
        # 未削除で、AまたはBのみとしか連結しなくなったものはキューに追加
        if (v not in deleted_set) and (0 in connect_label[v]):
            queue.appendleft(v)
        
    deleted_set.add(n)

# 全て削除していたらNo, そうでなければYes
print("Yes" if len(deleted_set) != N else "No")

Submission status: Accepted

Solution code:
import sys

n, m = map(int, input().split())
s = input()
to_a = [set() for _ in range(n)]
to_b = [set() for _ in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	if s[a-1] == "A":
		if s[b-1] == "A":
			to_a[a-1].add(b-1)
			to_a[b-1].add(a-1)
		else:
			to_b[a-1].add(b-1)
			to_a[b-1].add(a-1)
	if s[a-1] == "B":
		if s[b-1] == "B":
			to_b[a-1].add(b-1)
			to_b[b-1].add(a-1)
		else:
			to_a[a-1].add(b-1)
			to_b[b-1].add(a-1)

not_valid = set([i for i in range(n) if len(to_a[i]) * len(to_b[i]) == 0])
cnt = 0
#print(not_valid)

while not_valid:
	node = not_valid.pop()
	#print(node)
	cnt += 1

	for next_node in to_a[node]:
		if next_node == node:
			continue
		if s[node] == "A":
			to_a[next_node].remove(node)
		else:
			to_b[next_node].remove(node)

		if len(to_a[next_node]) * len(to_b[next_node]) == 0:
			not_valid.add(next_node)

	for next_node in to_b[node]:
		if next_node == node:
			continue
		if s[node] == "A":
			to_a[next_node].remove(node)
		else:
			to_b[next_node].remove(node)

		if len(to_a[next_node]) * len(to_b[next_node]) == 0:
			not_valid.add(next_node)

	#print(not_valid)

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

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
GC027 C
"""

n,m = map(int,input().split())
s = bytes(input(),'utf-8')
ali = [0 for i in range(n)]
bli = [0 for i in range(n)]
import array as ar
remain = ar.array('b',[1 for i in range(n)])
from collections import defaultdict
graphAB = defaultdict(list)

for i in range(m):
    u,v=map(int,input().split())
    graphAB[u].append(v)
    graphAB[v].append(u)



def incrementAB(node,adj):
    if s[adj-1] == 65:
        ali[node-1]+=1
    if s[adj-1] == 66:
        bli[node-1]+=1

def decrementAB(node,adj):
    if s[adj-1] == 65:
        ali[node-1]-=1
    if s[adj-1] == 66:
        bli[node-1]-=1


def adjAB(node):
    if ali[node-1] and bli[node-1]:
        return(True)
    else:
        return(False)

graphvers = set(graphAB.keys())
visitset = set()
for i in range(1,n+1):
    if not i in graphvers:
        remain[i-1] = 0
    else:
        for j in graphAB[i]:
            incrementAB(i,j)
        if not adjAB(i):
            visitset.add(i)
            remain[i-1] = 0

#print(s)
while bool(visitset):
    i = visitset.pop()
    for j in filter(lambda x:remain[x-1],graphAB[i]):
        #print('loop')
        decrementAB(j,i)
        if not adjAB(j):
            visitset.add(j)
            remain[j-1] = 0

if set(remain)=={0}:
    print('No')
else:
    print('Yes')

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
GC027 C
"""

n,m = map(int,input().split())
s = bytearray(input(),'utf-8')
ali = [0 for i in range(n)]
bli = [0 for i in range(n)]
from collections import defaultdict
graphAB = defaultdict(list)

for i in range(m):
    u,v=map(int,input().split())
    graphAB[u].append(v)
    graphAB[v].append(u)



def incrementAB(node,adj):
    if s[adj-1] == 65:
        ali[node-1]+=1
    if s[adj-1] == 66:
        bli[node-1]+=1

def decrementAB(node,adj):
    if s[adj-1] == 65:
        ali[node-1]-=1
    if s[adj-1] == 66:
        bli[node-1]-=1


def adjAB(node):
    if ali[node-1] and bli[node-1]:
        return(True)
    else:
        return(False)

graphvers = set(graphAB.keys())
visitset = set()
for i in range(1,n+1):
    if not i in graphvers:
        s[i-1] = 67
    else:
        for j in graphAB[i]:
            incrementAB(i,j)
        if not adjAB(i):
            visitset.add(i)

while bool(visitset):
    #print(graphAB)
    #print(graphABopp)
    #print(abli)
    i = visitset.pop()
    for j in filter(lambda x: s[x-1]!=67,graphAB[i]):
        decrementAB(j,i)
        if not adjAB(j):
            visitset.add(j)
    s[i-1] = 67

#print(graphAB)
#print(graphABopp)

sset= set(s)
sset.add(67)
sset.remove(67)
if bool(sset):
    print('Yes')
else:
    print('No')