def    lowerCAmelCase_ (     __A							)     ->				bool:







      '''simple docstring'''


      UpperCAmelCase__								=  set()
      # To detect a back edge, keep track of vertices currently in the recursion stack
      UpperCAmelCase__								=  set()
      return any(
          node not in visited and depth_first_search(__A,  __A,  __A,  __A							)
          for node in graph							)




def    lowerCAmelCase_ (     __A,  __A,  __A,  __A							)     ->				bool:







      '''simple docstring'''


      visited.add(__A							)
      rec_stk.add(__A							)

      for node in graph[vertex]:
            if node not in visited:
                  if depth_first_search(__A,  __A,  __A,  __A							):
                        return True
            elif node in rec_stk:
                  return True

    # The node needs to be removed from recursion stack before function ends
      rec_stk.remove(__A							)
      return False


if __name__ == "__main__":
      from doctest import testmod

      testmod()




def    lowerCAmelCase_ (     __A,  __A							)     ->				float:







      '''simple docstring'''


      def get_matched_characters(__A,  __A							) -> str:
            UpperCAmelCase__								=  []
            UpperCAmelCase__								=  min(len(_stra							),  len(_stra							)							) // 2
            for i, l in enumerate(_stra							):
                  UpperCAmelCase__								=  int(max(0,  i - limit							)							)
                  UpperCAmelCase__								=  int(min(i + limit + 1,  len(_stra							)							)							)
                  if l in _stra[left:right]:
                        matched.append(__A							)
                        UpperCAmelCase__								=  f"""{_stra[0:_stra.index(__A							)]} {_stra[_stra.index(__A							) + 1:]}"""

            return "".join(__A							)

      # matching characters
      UpperCAmelCase__								=  get_matched_characters(__A,  __A							)
      UpperCAmelCase__								=  get_matched_characters(__A,  __A							)
      UpperCAmelCase__								=  len(__A							)

      # transposition
      UpperCAmelCase__								=  (
          len([(ca, ca) for ca, ca in zip(__A,  __A							) if ca != ca]							) // 2
      )

      if not match_count:
            UpperCAmelCase__								=  0.0
      else:
            UpperCAmelCase__								=  (
                1
                / 3
                * (
                    match_count / len(__A							)
                    + match_count / len(__A							)
                    + (match_count - transpositions) / match_count
                )
            )

      # common prefix up to 4 characters
      UpperCAmelCase__								=  0
      for ca, ca in zip(stra[:4],  stra[:4]							):
            if ca == ca:
                  prefix_len += 1
            else:
                  break

      return jaro + 0.1 * prefix_len * (1 - jaro)


if __name__ == "__main__":
      import doctest

      doctest.testmod()
      print(jaro_winkler('hello', 'world'))



