




def 			lowerCamelCase_		(       UpperCamelCase__				:      str      )     ->       str:





				"""simple docstring"""


				__lowerCamelCase		       =    0

				# if input_string is "aba" than new_input_string become "a|b|a"
				__lowerCamelCase		       =    ''
				__lowerCamelCase		       =    ''

				# append each character + "|" in new_string for range(0, length-1)
				for i in input_string[: len(_lowerCamelCase      ) - 1]:
								new_input_string += i + "|"
				# append last character
				new_input_string += input_string[-1]

				# we will store the starting and ending of previous furthest ending palindromic
				# substring
				__lowerCamelCase       ,						__lowerCamelCase		       =    0, 0

				# length[i] shows the length of palindromic substring with center i
				__lowerCamelCase		       =    [1 for i in range(len(_lowerCamelCase      )      )]

				# for each character in new_string find corresponding palindromic string
				__lowerCamelCase		       =    0
				for j in range(len(_lowerCamelCase      )      ):
								__lowerCamelCase		       =    1 if j > r else min(length[l + r - j] // 2 ,     r - j + 1      )
								while (
								    j - k >= 0
								    and j + k < len(_lowerCamelCase      )
								    and new_input_string[k + j] == new_input_string[j - k]
								):
												k += 1

								__lowerCamelCase		       =    2 * k - 1

								# does this string is ending after the previously explored end (that is r) ?
								# if yes the update the new r to the last index of this
								if j + k - 1 > r:
												__lowerCamelCase		       =    j - k + 1  # noqa: E741
												__lowerCamelCase		       =    j + k - 1

								# update max_length and start position
								if max_length < length[j]:
												__lowerCamelCase		       =    length[j]
												__lowerCamelCase		       =    j

								# create that string
				__lowerCamelCase		       =    new_input_string[start - max_length // 2 : start + max_length // 2 + 1]
				for i in s:
								if i != "|":
												output_string += i

				return output_string


if __name__ == "__main__":
					import doctest

					doctest.testmod()










"""simple docstring"""





from __future__ import annotations

from typing import Generic, TypeVar

_SCREAMING_SNAKE_CASE					:				Optional[Any]					    =						TypeVar('''T''')






class      a						(					Generic[T]		):






    def __init__(       self     :							List[str]       ,						__SCREAMING_SNAKE_CASE     :							T					)     ->		None:
      lowerCamelCase_         =						data
      lowerCamelCase_         =						self
      lowerCamelCase_         =						0






class      a						(					Generic[T]		):






    def __init__(       self     :							Any					)     ->		None:
      # map from node name to the node object
      lowerCamelCase_         =						{}






    def    UpperCamelCase       (       self     :							List[str]       ,						__SCREAMING_SNAKE_CASE     :							T					)     ->		None:
      # create a new set with x as its member
      lowerCamelCase_         =						DisjointSetTreeNode(__SCREAMING_SNAKE_CASE					)






    def    UpperCamelCase       (       self     :							Optional[int]       ,						__SCREAMING_SNAKE_CASE     :							T					)     ->		DisjointSetTreeNode[T]:
      # find the set x belongs to (with path-compression)
      lowerCamelCase_         =						self.map[data]
      if elem_ref != elem_ref.parent:
        lowerCamelCase_         =						self.find_set(elem_ref.parent.data					)
      return elem_ref.parent






    def    UpperCamelCase       (       self     :							str       ,						__SCREAMING_SNAKE_CASE     :							DisjointSetTreeNode[T]       ,						__SCREAMING_SNAKE_CASE     :							DisjointSetTreeNode[T]					)     ->		None:
      # helper function for union operation
      if nodea.rank > nodea.rank:
        lowerCamelCase_         =						nodea
      else:
        lowerCamelCase_         =						nodea
        if nodea.rank == nodea.rank:
          nodea.rank += 1






    def    UpperCamelCase       (       self     :							List[str]       ,						__SCREAMING_SNAKE_CASE     :							T       ,						__SCREAMING_SNAKE_CASE     :							T					)     ->		None:
      # merge 2 disjoint sets
      self.link(self.find_set(__SCREAMING_SNAKE_CASE					)       ,						self.find_set(__SCREAMING_SNAKE_CASE					)					)






class      a						(					Generic[T]		):






    def __init__(       self     :							Optional[int]					)     ->		None:
      # connections: map from the node to the neighbouring nodes (with weights)
      lowerCamelCase_         =						{}






    def    UpperCamelCase       (       self     :							Optional[int]       ,						__SCREAMING_SNAKE_CASE     :							T					)     ->		None:
      # add a node ONLY if its not present in the graph
      if node not in self.connections:
        lowerCamelCase_         =						{}






    def    UpperCamelCase       (       self     :							Tuple       ,						__SCREAMING_SNAKE_CASE     :							T       ,						__SCREAMING_SNAKE_CASE     :							T       ,						__SCREAMING_SNAKE_CASE     :							int					)     ->		None:
      # add an edge with the given weight
      self.add_node(__SCREAMING_SNAKE_CASE					)
      self.add_node(__SCREAMING_SNAKE_CASE					)
      lowerCamelCase_         =						weight
      lowerCamelCase_         =						weight






    def    UpperCamelCase       (       self     :							List[Any]					)     ->		GraphUndirectedWeighted[T]:
      lowerCamelCase_         =						[]
      lowerCamelCase_         =						set()
      for start in self.connections:
        for end in self.connections[start]:
          if (start, end) not in seen:
            seen.add((end, start)					)
            edges.append((start, end, self.connections[start][end])					)
      edges.sort(key=lambda __SCREAMING_SNAKE_CASE					: x[2]					)

      # creating the disjoint set
      lowerCamelCase_         =						DisjointSetTree[T]()
      for node in self.connections:
        disjoint_set.make_set(__SCREAMING_SNAKE_CASE					)

      # MST generation
      lowerCamelCase_         =						0
      lowerCamelCase_         =						0
      lowerCamelCase_         =						GraphUndirectedWeighted[T]()
      while num_edges < len(self.connections					) - 1:
        lowerCamelCase_     ,	lowerCamelCase_     ,	lowerCamelCase_         =						edges[index]
        index += 1
        lowerCamelCase_         =						disjoint_set.find_set(__SCREAMING_SNAKE_CASE					)
        lowerCamelCase_         =						disjoint_set.find_set(__SCREAMING_SNAKE_CASE					)
        if parent_u != parent_v:
          num_edges += 1
          graph.add_edge(__SCREAMING_SNAKE_CASE       ,						__SCREAMING_SNAKE_CASE       ,						__SCREAMING_SNAKE_CASE					)
          disjoint_set.union(__SCREAMING_SNAKE_CASE       ,						__SCREAMING_SNAKE_CASE					)
      return graph




