


from collections import deque
from math import floor
from random import random
from time import time

class       __magic_name__	:


     def __init__(      self							:     str			)  ->      Optional[Any]:





      '''simple docstring'''






      UpperCamelCase__					:    Union[str, Any]          =   {}


     def      UpperCAmelCase__	(      self							:     List[Any]							,	lowerCamelCase__							:     Union[str, Any]							,	lowerCamelCase__							:     List[Any]							,	lowerCamelCase__							:     Tuple=1			)  ->      str:





      '''simple docstring'''






      if self.graph.get(lowerCamelCase__			):
       if self.graph[u].count([w, v]			) == 0:
        self.graph[u].append([w, v]			)
      else:
       UpperCamelCase__					:    Tuple          =   [[w, v]]
      if not self.graph.get(lowerCamelCase__			):
       UpperCamelCase__					:    Optional[int]          =   []


     def      UpperCAmelCase__	(      self							:     Dict			)  ->      str:





      '''simple docstring'''






      return list(self.graph			)


     def      UpperCAmelCase__	(      self							:     Dict							,	lowerCamelCase__							:     Dict							,	lowerCamelCase__							:     List[str]			)  ->      str:





      '''simple docstring'''






      if self.graph.get(lowerCamelCase__			):
       for _ in self.graph[u]:
        if _[1] == v:
         self.graph[u].remove(lowerCamelCase__			)


     def      UpperCAmelCase__	(      self							:     int							,	lowerCamelCase__							:     List[str]=-2							,	lowerCamelCase__							:     str=-1			)  ->      int:





      '''simple docstring'''






      if s == d:
       return []
      UpperCamelCase__					:    Dict          =   []
      UpperCamelCase__					:    Union[str, Any]          =   []
      if s == -2:
       UpperCamelCase__					:    Tuple          =   list(self.graph			)[0]
      stack.append(lowerCamelCase__			)
      visited.append(lowerCamelCase__			)
      UpperCamelCase__					:    Optional[int]          =   s

      while True:
       # check if there is any non isolated nodes
       if len(self.graph[s]			) != 0:
        UpperCamelCase__					:    int          =   s
        for node in self.graph[s]:
         if visited.count(node[1]			) < 1:
          if node[1] == d:
           visited.append(lowerCamelCase__			)
           return visited
          else:
           stack.append(node[1]			)
           visited.append(node[1]			)
           UpperCamelCase__					:    List[str]          =   node[1]
           break

            # check if all the children are visited
       if s == ss:
        stack.pop()
        if len(lowerCamelCase__			) != 0:
         UpperCamelCase__					:    str          =   stack[len(lowerCamelCase__			) - 1]
       else:
        UpperCamelCase__					:    Optional[Any]          =   ss

       # check if se have reached the starting point
       if len(lowerCamelCase__			) == 0:
        return visited


     def      UpperCAmelCase__	(      self							:     Tuple							,	lowerCamelCase__							:     Optional[Any]=-1			)  ->      Union[str, Any]:





      '''simple docstring'''






      if c == -1:
       UpperCamelCase__					:    Any          =   floor(random() * 10000			) + 10
      for i in range(lowerCamelCase__			):
       # every vertex has max 100 edges
       for _ in range(floor(random() * 102			) + 1			):
        UpperCamelCase__					:    Optional[int]          =   floor(random() * c			) + 1
        if n != i:
         self.add_pair(lowerCamelCase__							,	lowerCamelCase__							,	1			)


     def      UpperCAmelCase__	(      self							:     int							,	lowerCamelCase__							:     Dict=-2			)  ->      Any:





      '''simple docstring'''






      UpperCamelCase__					:    Tuple          =   deque()
      UpperCamelCase__					:    List[Any]          =   []
      if s == -2:
       UpperCamelCase__					:    List[str]          =   list(self.graph			)[0]
      d.append(lowerCamelCase__			)
      visited.append(lowerCamelCase__			)
      while d:
       UpperCamelCase__					:    Dict          =   d.popleft()
       if len(self.graph[s]			) != 0:
        for node in self.graph[s]:
         if visited.count(node[1]			) < 1:
          d.append(node[1]			)
          visited.append(node[1]			)
      return visited


     def      UpperCAmelCase__	(      self							:     List[str]							,	lowerCamelCase__							:     int			)  ->      List[str]:





      '''simple docstring'''






      UpperCamelCase__					:    Optional[Any]          =   0
      for x in self.graph:
       for y in self.graph[x]:
        if y[1] == u:
         count += 1
      return count


     def      UpperCAmelCase__	(      self							:     Optional[int]							,	lowerCamelCase__							:     int			)  ->      List[Any]:





      '''simple docstring'''






      return len(self.graph[u]			)


     def      UpperCAmelCase__	(      self							:     Optional[int]							,	lowerCamelCase__							:     Dict=-2			)  ->      Optional[Any]:





      '''simple docstring'''






      UpperCamelCase__					:    Any          =   []
      UpperCamelCase__					:    List[str]          =   []
      if s == -2:
       UpperCamelCase__					:    Union[str, Any]          =   list(self.graph			)[0]
      stack.append(lowerCamelCase__			)
      visited.append(lowerCamelCase__			)
      UpperCamelCase__					:    str          =   s
      UpperCamelCase__					:    str          =   []

      while True:
       # check if there is any non isolated nodes
       if len(self.graph[s]			) != 0:
        UpperCamelCase__					:    Tuple          =   s
        for node in self.graph[s]:
         if visited.count(node[1]			) < 1:
          stack.append(node[1]			)
          visited.append(node[1]			)
          UpperCamelCase__					:    str          =   node[1]
          break

            # check if all the children are visited
       if s == ss:
        sorted_nodes.append(stack.pop()			)
        if len(lowerCamelCase__			) != 0:
         UpperCamelCase__					:    Any          =   stack[len(lowerCamelCase__			) - 1]
       else:
        UpperCamelCase__					:    Dict          =   ss

       # check if se have reached the starting point
       if len(lowerCamelCase__			) == 0:
        return sorted_nodes


     def      UpperCAmelCase__	(      self							:     Dict			)  ->      Optional[int]:





      '''simple docstring'''






      UpperCamelCase__					:    Any          =   []
      UpperCamelCase__					:    Optional[Any]          =   []
      UpperCamelCase__					:    Any          =   list(self.graph			)[0]
      stack.append(lowerCamelCase__			)
      visited.append(lowerCamelCase__			)
      UpperCamelCase__					:    Optional[int]          =   -2
      UpperCamelCase__					:    Optional[int]          =   []
      UpperCamelCase__					:    List[Any]          =   s
      UpperCamelCase__					:    List[Any]          =   False
      UpperCamelCase__					:    List[str]          =   set()

      while True:
       # check if there is any non isolated nodes
       if len(self.graph[s]			) != 0:
        UpperCamelCase__					:    List[str]          =   s
        for node in self.graph[s]:
         if (
             visited.count(node[1]			) > 0
             and node[1] != parent
             and indirect_parents.count(node[1]			) > 0
             and not on_the_way_back
         ):
          UpperCamelCase__					:    Optional[int]          =   len(lowerCamelCase__			) - 1
          while len_stack >= 0:
           if stack[len_stack] == node[1]:
            anticipating_nodes.add(node[1]			)
            break
           else:
            anticipating_nodes.add(stack[len_stack]			)
            len_stack -= 1
         if visited.count(node[1]			) < 1:
          stack.append(node[1]			)
          visited.append(node[1]			)
          UpperCamelCase__					:    Union[str, Any]          =   node[1]
          break

            # check if all the children are visited
       if s == ss:
        stack.pop()
        UpperCamelCase__					:    Tuple          =   True
        if len(lowerCamelCase__			) != 0:
         UpperCamelCase__					:    str          =   stack[len(lowerCamelCase__			) - 1]
       else:
        UpperCamelCase__					:    Optional[Any]          =   False
        indirect_parents.append(lowerCamelCase__			)
        UpperCamelCase__					:    int          =   s
        UpperCamelCase__					:    Tuple          =   ss

       # check if se have reached the starting point
       if len(lowerCamelCase__			) == 0:
        return list(lowerCamelCase__			)


     def      UpperCAmelCase__	(      self							:     Optional[Any]			)  ->      Optional[Any]:





      '''simple docstring'''






      UpperCamelCase__					:    int          =   []
      UpperCamelCase__					:    Optional[int]          =   []
      UpperCamelCase__					:    Tuple          =   list(self.graph			)[0]
      stack.append(lowerCamelCase__			)
      visited.append(lowerCamelCase__			)
      UpperCamelCase__					:    Tuple          =   -2
      UpperCamelCase__					:    str          =   []
      UpperCamelCase__					:    Any          =   s
      UpperCamelCase__					:    Union[str, Any]          =   False
      UpperCamelCase__					:    Union[str, Any]          =   set()

      while True:
       # check if there is any non isolated nodes
       if len(self.graph[s]			) != 0:
        UpperCamelCase__					:    List[Any]          =   s
        for node in self.graph[s]:
         if (
             visited.count(node[1]			) > 0
             and node[1] != parent
             and indirect_parents.count(node[1]			) > 0
             and not on_the_way_back
         ):
          UpperCamelCase__					:    Optional[Any]          =   len(lowerCamelCase__			) - 1
          while len_stack_minus_one >= 0:
           if stack[len_stack_minus_one] == node[1]:
            anticipating_nodes.add(node[1]			)
            break
           else:
            return True
         if visited.count(node[1]			) < 1:
          stack.append(node[1]			)
          visited.append(node[1]			)
          UpperCamelCase__					:    Tuple          =   node[1]
          break

            # check if all the children are visited
       if s == ss:
        stack.pop()
        UpperCamelCase__					:    Any          =   True
        if len(lowerCamelCase__			) != 0:
         UpperCamelCase__					:    Dict          =   stack[len(lowerCamelCase__			) - 1]
       else:
        UpperCamelCase__					:    Any          =   False
        indirect_parents.append(lowerCamelCase__			)
        UpperCamelCase__					:    List[str]          =   s
        UpperCamelCase__					:    Union[str, Any]          =   ss

       # check if se have reached the starting point
       if len(lowerCamelCase__			) == 0:
        return False


     def      UpperCAmelCase__	(      self							:     Tuple							,	lowerCamelCase__							:     str=-2							,	lowerCamelCase__							:     Union[str, Any]=-1			)  ->      List[Any]:





      '''simple docstring'''






      UpperCamelCase__					:    str          =   time()
      self.dfs(lowerCamelCase__							,	lowerCamelCase__			)
      UpperCamelCase__					:    List[Any]          =   time()
      return end - begin


     def      UpperCAmelCase__	(      self							:     Any							,	lowerCamelCase__							:     Dict=-2			)  ->      Tuple:





      '''simple docstring'''






      UpperCamelCase__					:    Any          =   time()
      self.bfs(lowerCamelCase__			)
      UpperCamelCase__					:    str          =   time()
      return end - begin



class       __magic_name__	:


     def __init__(      self							:     int			)  ->      Union[str, Any]:





      '''simple docstring'''






      UpperCamelCase__					:    int          =   {}


     def      UpperCAmelCase__	(      self							:     List[Any]							,	lowerCamelCase__							:     List[str]							,	lowerCamelCase__							:     str							,	lowerCamelCase__							:     Optional[int]=1			)  ->      Any:





      '''simple docstring'''






      if self.graph.get(lowerCamelCase__			):
       # if there already is a edge
       if self.graph[u].count([w, v]			) == 0:
        self.graph[u].append([w, v]			)
      else:
       # if u does not exist
       UpperCamelCase__					:    Optional[Any]          =   [[w, v]]
      # add the other way
      if self.graph.get(lowerCamelCase__			):
       # if there already is a edge
       if self.graph[v].count([w, u]			) == 0:
        self.graph[v].append([w, u]			)
      else:
       # if u does not exist
       UpperCamelCase__					:    int          =   [[w, u]]


     def      UpperCAmelCase__	(      self							:     Dict							,	lowerCamelCase__							:     List[str]							,	lowerCamelCase__							:     Optional[int]			)  ->      List[Any]:





      '''simple docstring'''






      if self.graph.get(lowerCamelCase__			):
       for _ in self.graph[u]:
        if _[1] == v:
         self.graph[u].remove(lowerCamelCase__			)
        # the other way round
      if self.graph.get(lowerCamelCase__			):
       for _ in self.graph[v]:
        if _[1] == u:
         self.graph[v].remove(lowerCamelCase__			)


     def      UpperCAmelCase__	(      self							:     List[Any]							,	lowerCamelCase__							:     int=-2							,	lowerCamelCase__							:     int=-1			)  ->      Optional[int]:





      '''simple docstring'''






      if s == d:
       return []
      UpperCamelCase__					:    Any          =   []
      UpperCamelCase__					:    Optional[int]          =   []
      if s == -2:
       UpperCamelCase__					:    List[str]          =   list(self.graph			)[0]
      stack.append(lowerCamelCase__			)
      visited.append(lowerCamelCase__			)
      UpperCamelCase__					:    List[str]          =   s

      while True:
       # check if there is any non isolated nodes
       if len(self.graph[s]			) != 0:
        UpperCamelCase__					:    List[Any]          =   s
        for node in self.graph[s]:
         if visited.count(node[1]			) < 1:
          if node[1] == d:
           visited.append(lowerCamelCase__			)
           return visited
          else:
           stack.append(node[1]			)
           visited.append(node[1]			)
           UpperCamelCase__					:    int          =   node[1]
           break

            # check if all the children are visited
       if s == ss:
        stack.pop()
        if len(lowerCamelCase__			) != 0:
         UpperCamelCase__					:    Union[str, Any]          =   stack[len(lowerCamelCase__			) - 1]
       else:
        UpperCamelCase__					:    Dict          =   ss

       # check if se have reached the starting point
       if len(lowerCamelCase__			) == 0:
        return visited


     def      UpperCAmelCase__	(      self							:     List[Any]							,	lowerCamelCase__							:     List[Any]=-1			)  ->      int:





      '''simple docstring'''






      if c == -1:
       UpperCamelCase__					:    Union[str, Any]          =   floor(random() * 10000			) + 10
      for i in range(lowerCamelCase__			):
       # every vertex has max 100 edges
       for _ in range(floor(random() * 102			) + 1			):
        UpperCamelCase__					:    Optional[Any]          =   floor(random() * c			) + 1
        if n != i:
         self.add_pair(lowerCamelCase__							,	lowerCamelCase__							,	1			)


     def      UpperCAmelCase__	(      self							:     Union[str, Any]							,	lowerCamelCase__							:     str=-2			)  ->      str:





      '''simple docstring'''






      UpperCamelCase__					:    List[str]          =   deque()
      UpperCamelCase__					:    Optional[Any]          =   []
      if s == -2:
       UpperCamelCase__					:    Dict          =   list(self.graph			)[0]
      d.append(lowerCamelCase__			)
      visited.append(lowerCamelCase__			)
      while d:
       UpperCamelCase__					:    Optional[Any]          =   d.popleft()
       if len(self.graph[s]			) != 0:
        for node in self.graph[s]:
         if visited.count(node[1]			) < 1:
          d.append(node[1]			)
          visited.append(node[1]			)
      return visited


     def      UpperCAmelCase__	(      self							:     Union[str, Any]							,	lowerCamelCase__							:     Optional[int]			)  ->      Tuple:





      '''simple docstring'''






      return len(self.graph[u]			)


     def      UpperCAmelCase__	(      self							:     Dict			)  ->      Union[str, Any]:





      '''simple docstring'''






      UpperCamelCase__					:    Optional[Any]          =   []
      UpperCamelCase__					:    Any          =   []
      UpperCamelCase__					:    int          =   list(self.graph			)[0]
      stack.append(lowerCamelCase__			)
      visited.append(lowerCamelCase__			)
      UpperCamelCase__					:    Union[str, Any]          =   -2
      UpperCamelCase__					:    Any          =   []
      UpperCamelCase__					:    str          =   s
      UpperCamelCase__					:    str          =   False
      UpperCamelCase__					:    str          =   set()

      while True:
       # check if there is any non isolated nodes
       if len(self.graph[s]			) != 0:
        UpperCamelCase__					:    List[Any]          =   s
        for node in self.graph[s]:
         if (
             visited.count(node[1]			) > 0
             and node[1] != parent
             and indirect_parents.count(node[1]			) > 0
             and not on_the_way_back
         ):
          UpperCamelCase__					:    Any          =   len(lowerCamelCase__			) - 1
          while len_stack >= 0:
           if stack[len_stack] == node[1]:
            anticipating_nodes.add(node[1]			)
            break
           else:
            anticipating_nodes.add(stack[len_stack]			)
            len_stack -= 1
         if visited.count(node[1]			) < 1:
          stack.append(node[1]			)
          visited.append(node[1]			)
          UpperCamelCase__					:    Union[str, Any]          =   node[1]
          break

            # check if all the children are visited
       if s == ss:
        stack.pop()
        UpperCamelCase__					:    str          =   True
        if len(lowerCamelCase__			) != 0:
         UpperCamelCase__					:    Optional[int]          =   stack[len(lowerCamelCase__			) - 1]
       else:
        UpperCamelCase__					:    Optional[int]          =   False
        indirect_parents.append(lowerCamelCase__			)
        UpperCamelCase__					:    Dict          =   s
        UpperCamelCase__					:    Union[str, Any]          =   ss

       # check if se have reached the starting point
       if len(lowerCamelCase__			) == 0:
        return list(lowerCamelCase__			)


     def      UpperCAmelCase__	(      self							:     Dict			)  ->      List[Any]:





      '''simple docstring'''






      UpperCamelCase__					:    Optional[Any]          =   []
      UpperCamelCase__					:    Dict          =   []
      UpperCamelCase__					:    Tuple          =   list(self.graph			)[0]
      stack.append(lowerCamelCase__			)
      visited.append(lowerCamelCase__			)
      UpperCamelCase__					:    Any          =   -2
      UpperCamelCase__					:    Any          =   []
      UpperCamelCase__					:    Tuple          =   s
      UpperCamelCase__					:    List[Any]          =   False
      UpperCamelCase__					:    Optional[int]          =   set()

      while True:
       # check if there is any non isolated nodes
       if len(self.graph[s]			) != 0:
        UpperCamelCase__					:    Union[str, Any]          =   s
        for node in self.graph[s]:
         if (
             visited.count(node[1]			) > 0
             and node[1] != parent
             and indirect_parents.count(node[1]			) > 0
             and not on_the_way_back
         ):
          UpperCamelCase__					:    List[Any]          =   len(lowerCamelCase__			) - 1
          while len_stack_minus_one >= 0:
           if stack[len_stack_minus_one] == node[1]:
            anticipating_nodes.add(node[1]			)
            break
           else:
            return True
         if visited.count(node[1]			) < 1:
          stack.append(node[1]			)
          visited.append(node[1]			)
          UpperCamelCase__					:    List[str]          =   node[1]
          break

            # check if all the children are visited
       if s == ss:
        stack.pop()
        UpperCamelCase__					:    Any          =   True
        if len(lowerCamelCase__			) != 0:
         UpperCamelCase__					:    int          =   stack[len(lowerCamelCase__			) - 1]
       else:
        UpperCamelCase__					:    str          =   False
        indirect_parents.append(lowerCamelCase__			)
        UpperCamelCase__					:    Optional[Any]          =   s
        UpperCamelCase__					:    Dict          =   ss

       # check if se have reached the starting point
       if len(lowerCamelCase__			) == 0:
        return False


     def      UpperCAmelCase__	(      self							:     Union[str, Any]			)  ->      Tuple:





      '''simple docstring'''






      return list(self.graph			)


     def      UpperCAmelCase__	(      self							:     Optional[Any]							,	lowerCamelCase__							:     Tuple=-2							,	lowerCamelCase__							:     str=-1			)  ->      List[str]:





      '''simple docstring'''






      UpperCamelCase__					:    List[Any]          =   time()
      self.dfs(lowerCamelCase__							,	lowerCamelCase__			)
      UpperCamelCase__					:    Union[str, Any]          =   time()
      return end - begin


     def      UpperCAmelCase__	(      self							:     Optional[int]							,	lowerCamelCase__							:     List[Any]=-2			)  ->      Union[str, Any]:





      '''simple docstring'''






      UpperCamelCase__					:    Any          =   time()
      self.bfs(lowerCamelCase__			)
      UpperCamelCase__					:    str          =   time()
      return end - begin






import functools

def 			_a  (				SCREAMING_SNAKE_CASE	:				str    , SCREAMING_SNAKE_CASE	:				str     ):







 """simple docstring"""



 UpperCamelCase__					:    str          =   len(SCREAMING_SNAKE_CASE     )
 UpperCamelCase__					:    Optional[Any]          =   len(SCREAMING_SNAKE_CASE     )

 @functools.cache
 def min_distance(SCREAMING_SNAKE_CASE	:				int    , SCREAMING_SNAKE_CASE	:				int     ) -> int:
  # if first word index is overflow - delete all from the second word
  if indexa >= len_worda:
   return len_worda - indexa
  # if second word index is overflow - delete all from the first word
  if indexa >= len_worda:
   return len_worda - indexa
  UpperCamelCase__					:    Tuple          =   int(worda[indexa] != worda[indexa]     )  # current letters not identical
  return min(
      1 + min_distance(indexa + 1    , SCREAMING_SNAKE_CASE     )    , 1 + min_distance(SCREAMING_SNAKE_CASE    , indexa + 1     )    , diff + min_distance(indexa + 1    , indexa + 1     )    , )

 return min_distance(0    , 0     )


if __name__ == "__main__":
       import doctest

       doctest.testmod()


