


"""simple docstring"""






from __future__ import annotations

from queue import Queue
def    A_ ( _lowerCAmelCase  :       int,  _lowerCAmelCase  :       int							):






     """simple docstring"""

     a ^= b
     b ^= a
     a ^= b
     return a, b
def    A_ ( _lowerCAmelCase  :       int,  _lowerCAmelCase  :       list[list[int]]							):






     """simple docstring"""

     _a     						=					1
     while (1 << j) < max_node:
          for i in range(1,  max_node + 1							):
               _a     						=					parent[j - 1][parent[j - 1][i]]
          j += 1
     return parent
def    A_ ( _lowerCAmelCase  :       int,  _lowerCAmelCase  :       int,  _lowerCAmelCase  :       list[int],  _lowerCAmelCase  :       list[list[int]]							):






     """simple docstring"""

     if level[u] < level[v]:
          _a						,   _a     						=					swap(_lowerCAmelCase,  _lowerCAmelCase							)
     # making depth of u same as depth of v
     for i in range(18,  -1,  -1							):
          if level[u] - (1 << i) >= level[v]:
               _a     						=					parent[i][u]
    # at the same depth if u==v that mean lca is found
     if u == v:
          return u
     # moving both nodes upwards till lca in found
     for i in range(18,  -1,  -1							):
          if parent[i][u] not in [0, parent[i][v]]:
               _a						,   _a     						=					parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
     return parent[0][u]
def    A_ ( _lowerCAmelCase  :       list[int],  _lowerCAmelCase  :       list[list[int]],  _lowerCAmelCase  :       int,  _lowerCAmelCase  :       dict[int, list[int]],  _lowerCAmelCase  :       int = 1,  ):






     """simple docstring"""

     _a     						=					0
     _a     						=					Queue(maxsize=_lowerCAmelCase							)
     q.put(_lowerCAmelCase							)
     while q.qsize() != 0:
          _a     						=					q.get()
          for v in graph[u]:
               if level[v] == -1:
                    _a     						=					level[u] + 1
                    q.put(_lowerCAmelCase							)
                    _a     						=					u
     return level, parent
def    A_ ( ):






     """simple docstring"""

     _a     						=					13
     # initializing with 0
     _a     						=					[[0 for _ in range(max_node + 10							)] for _ in range(20							)]
     # initializing with -1 which means every node is unvisited
     _a     						=					[-1 for _ in range(max_node + 10							)]
     _a     						=					{
         1: [2, 3, 4],
         2: [5],
         3: [6, 7],
         4: [8],
         5: [9, 10],
         6: [11],
         7: [],
         8: [12, 13],
         9: [],
         10: [],
         11: [],
         12: [],
         13: [],
     }
     _a						,   _a     						=					breadth_first_search(_lowerCAmelCase,  _lowerCAmelCase,  _lowerCAmelCase,  _lowerCAmelCase,  1							)
     _a     						=					create_sparse(_lowerCAmelCase,  _lowerCAmelCase							)
     print('''LCA of node 1 and 3 is: ''',  lowest_common_ancestor(1,  3,  _lowerCAmelCase,  _lowerCAmelCase							)							)
     print('''LCA of node 5 and 6 is: ''',  lowest_common_ancestor(5,  6,  _lowerCAmelCase,  _lowerCAmelCase							)							)
     print('''LCA of node 7 and 11 is: ''',  lowest_common_ancestor(7,  11,  _lowerCAmelCase,  _lowerCAmelCase							)							)
     print('''LCA of node 6 and 7 is: ''',  lowest_common_ancestor(6,  7,  _lowerCAmelCase,  _lowerCAmelCase							)							)
     print('''LCA of node 4 and 12 is: ''',  lowest_common_ancestor(4,  12,  _lowerCAmelCase,  _lowerCAmelCase							)							)
     print('''LCA of node 8 and 8 is: ''',  lowest_common_ancestor(8,  8,  _lowerCAmelCase,  _lowerCAmelCase							)							)


if __name__ == "__main__":
   main()



"""simple docstring"""






def    A_ ( _lowerCAmelCase  :       str,  _lowerCAmelCase  :       str							):






     """simple docstring"""

     if len(_lowerCAmelCase							) < len(_lowerCAmelCase							):
          return levenshtein_distance(_lowerCAmelCase,  _lowerCAmelCase							)

     if len(_lowerCAmelCase							) == 0:
          return len(_lowerCAmelCase							)

     _a     						=					list(range(len(_lowerCAmelCase							) + 1							)							)

     for i, ca in enumerate(_lowerCAmelCase							):
          _a     						=					[i + 1]

          for j, ca in enumerate(_lowerCAmelCase							):
               # Calculate insertions, deletions and substitutions
               _a     						=					previous_row[j + 1] + 1
               _a     						=					current_row[j] + 1
               _a     						=					previous_row[j] + (ca != ca)

               # Get the minimum to append to the current row
               current_row.append(min(_lowerCAmelCase,  _lowerCAmelCase,  _lowerCAmelCase							)							)

          # Store the previous row
          _a     						=					current_row

     # Returns the last element (distance)
     return previous_row[-1]


if __name__ == "__main__":
   __snake_case												=							input('''Enter the first word:\n''').strip()
   __snake_case												=							input('''Enter the second word:\n''').strip()

   __snake_case												=							levenshtein_distance(first_word, second_word)
   print(f'Levenshtein distance between {first_word} and {second_word} is {result}')