output_description: If Nusook can make all strings consisting of `A` and `B`, print `Yes`;
  otherwise, print `No`.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      s
      a_1 b_1
      :
      a_{M} b_{M}
attempt: 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)]
  
  diffs = [set() for _ in range(N)]
  sames = [set() for _ in range(N)]
  for a, b in AB:
      a -= 1
      b -= 1
      if S[a] == S[b]:
          sames[a].add(b)
          sames[b].add(a)
      else:
          diffs[a].add(b)
          diffs[b].add(a)
  diffs = [list(s) for s in diffs]
  sames = [list(s) for s in sames]
  
  checked = [[False] * N for _ in range(2)]
  
  
  # @debug
  def dfs(v, pc=None, seen=None):
      seen = seen or set()
  
      if v in seen:
          return True
      seen.add(v)
      if pc is not None:
          checked[int(pc == "A")][v] = True
  
      if pc is None or pc == S[v]:
          ok = False
          for u in diffs[v]:
              if not checked[int(S[v] == "A")][u] and 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 sames[v]:
              if not checked[int(S[v] == "A")][u] and 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")
  
problem_description: 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`.
samples: [{"input": "2 3\n    AB\n    1 1\n    1 2\n    2 2", "output": "Yes\n    \n\n  * Since Nusook can visit Vertex 1 and Vertex 2 in any way he likes, he can make all strings consisting of `A` and `B`.\n\n![77e96cf8e213d606ddd8f3c3f8315d32.png](https://img.atcoder.jp/agc027/77e96cf8e213d606ddd8f3c3f8315d32.png)\n\n* * *"}, {"input": "4 3\n    ABAB\n    1 2\n    2 3\n    3 1", "output": "No\n    \n\n  * For example, Nusook cannot make `BB`.\n  * The given graph may not be connected.\n\n![1ab1411cb9d6ee023d14ca4e77c4b584.png](https://img.atcoder.jp/agc027/1ab1411cb9d6ee023d14ca4e77c4b584.png)\n\n* * *"}, {"input": "13 23\n    ABAAAABBBBAAB\n    7 1\n    10 6\n    1 11\n    2 10\n    2 8\n    2 11\n    11 12\n    8 3\n    7 12\n    11 2\n    13 13\n    11 9\n    4 1\n    9 7\n    9 6\n    8 13\n    8 6\n    4 10\n    8 7\n    4 3\n    2 1\n    8 12\n    6 9", "output": "Yes\n    \n\n* * *"}, {"input": "13 17\n    BBABBBAABABBA\n    7 1\n    7 9\n    11 12\n    3 9\n    11 9\n    2 1\n    11 5\n    12 11\n    10 8\n    1 11\n    1 8\n    7 7\n    9 10\n    8 8\n    8 12\n    6 2\n    13 11", "output": "No"}]