





def 	lowerCamelCase_		(							_UpperCamelCase					)						->		list[int]:






				"""simple docstring"""


				snake_case_		:       Optional[int]           =    [0 for i in range(len(_UpperCamelCase					)					)]

				# initialize interval's left pointer and right pointer
				snake_case_     ,				snake_case_		:       Tuple           =    0, 0

				for i in range(1					,							len(_UpperCamelCase					)					):
								# case when current index is inside the interval
								if i <= right_pointer:
												snake_case_		:       Any           =    min(right_pointer - i + 1					,							z_result[i - left_pointer]					)
												snake_case_		:       Tuple           =    min_edge

								while go_next(_UpperCamelCase					,							_UpperCamelCase					,							_UpperCamelCase					):
												z_result[i] += 1

								# if new index's result gives us more right interval,
								# we've to update left_pointer and right_pointer
								if i + z_result[i] - 1 > right_pointer:
												snake_case_     ,				snake_case_		:       int           =    i, i + z_result[i] - 1

				return z_result






def 	lowerCamelCase_		(							_UpperCamelCase					,							_UpperCamelCase					,							_UpperCamelCase					)						->		bool:






				"""simple docstring"""


				return i + z_result[i] < len(_UpperCamelCase					) and s[z_result[i]] == s[i + z_result[i]]






def 	lowerCamelCase_		(							_UpperCamelCase					,							_UpperCamelCase					)						->		int:






				"""simple docstring"""


				snake_case_		:       Tuple           =    0
				# concatenate 'pattern' and 'input_str' and call z_function
				# with concatenated string
				snake_case_		:       Union[str, Any]           =    z_function(pattern + input_str					)

				for val in z_result:
								# if value is greater then length of the pattern string
								# that means this index is starting position of substring
								# which is equal to pattern string
								if val >= len(_UpperCamelCase					):
												answer += 1

				return answer


if __name__ == "__main__":
	import doctest

	doctest.testmod()




from __future__ import annotations

from typing import Any




class       lowercase_					:





				def __init__(				self       ,  lowercase_)  -> None:
											a__      =num_of_nodes
											a__      =[]
											a__      ={}





				def 						__UpperCamelCase    (				self       ,  lowercase_       ,  lowercase_       ,  lowercase_)  -> None:
											self.m_edges.append([u_node, v_node, weight])





				def 						__UpperCamelCase    (				self       ,  lowercase_)  -> int:

											if self.m_component[u_node] == u_node:
																		return u_node
											return self.find_component(self.m_component[u_node])





				def 						__UpperCamelCase    (				self       ,  lowercase_)  -> None:

											if self.m_component[u_node] != u_node:
																		for k in self.m_component:
																									a__      =self.find_component(lowercase_)





				def 						__UpperCamelCase    (				self       ,  lowercase_       ,  lowercase_       ,  lowercase_)  -> None:

											if component_size[u_node] <= component_size[v_node]:
																		a__      =v_node
																		component_size[v_node] += component_size[u_node]
																		self.set_component(lowercase_)

											elif component_size[u_node] >= component_size[v_node]:
																		a__      =self.find_component(lowercase_)
																		component_size[u_node] += component_size[v_node]
																		self.set_component(lowercase_)





				def 						__UpperCamelCase    (				self)  -> None:
											a__      =[]
											a__      =0

											a__      =[-1] * self.m_num_of_nodes

											# A list of components (initialized to all of the nodes)
											for node in range(self.m_num_of_nodes):
																		self.m_component.update({node: node})
																		component_size.append(1)

											a__      =self.m_num_of_nodes

											while num_of_components > 1:
																		for edge in self.m_edges:
																									a__    ,     a__    ,     a__      =edge

																									a__      =self.m_component[u]
																									a__      =self.m_component[v]

																									if u_component != v_component:

																																for component in (u_component, v_component):
																																							if (
																																							    minimum_weight_edge[component] == -1
																																							    or minimum_weight_edge[component][2] > w
																																							):
																																														a__      =[u, v, w]

																		for edge in minimum_weight_edge:
																									if isinstance(lowercase_       ,  lowercase_):
																																a__    ,     a__    ,     a__      =edge

																																a__      =self.m_component[u]
																																a__      =self.m_component[v]

																																if u_component != v_component:
																																							mst_weight += w
																																							self.union(lowercase_       ,  lowercase_       ,  lowercase_)
																																							print(F"""Added edge [{u} - {v}]\nAdded weight: {w}\n""")
																																							num_of_components -= 1

																		a__      =[-1] * self.m_num_of_nodes
											print(F"""The total weight of the minimal spanning tree is: {mst_weight}""")







def   _lowercase(					):
							pass


if __name__ == "__main__":
	import doctest

	doctest.testmod()

