





'''simple docstring'''





class SCREAMING_SNAKE_CASE_ :





					"""simple docstring"""


					def __init__( self	):
										lowerCamelCase__       =       0
										lowerCamelCase__       =       0
										lowerCamelCase__       =       {}





					def 					__magic_name__ ( self	,  _lowerCAmelCase	):
										if vertex not in self.adjacency:
															lowerCamelCase__       =       {}
															self.num_vertices += 1





					def 					__magic_name__ ( self	,  _lowerCAmelCase	,  _lowerCAmelCase	,  _lowerCAmelCase	):
										self.add_vertex(_lowerCAmelCase	)
										self.add_vertex(_lowerCAmelCase	)

										if head == tail:
															return

										lowerCamelCase__       =       weight
										lowerCamelCase__       =       weight





					def 					__magic_name__ ( self	):
										lowerCamelCase__       =       self.get_edges()
										for edge in edges:
															lowerCamelCase__    ,		lowerCamelCase__    ,		lowerCamelCase__       =       edge
															edges.remove((tail, head, weight)	)
										for i in range(len(_lowerCAmelCase	)	):
															lowerCamelCase__       =       list(edges[i]	)

										edges.sort(key=lambda _lowerCAmelCase	: e[2]	)
										for i in range(len(_lowerCAmelCase	) - 1	):
															if edges[i][2] >= edges[i + 1][2]:
																				lowerCamelCase__       =       edges[i][2] + 1
										for edge in edges:
															lowerCamelCase__    ,		lowerCamelCase__    ,		lowerCamelCase__       =       edge
															lowerCamelCase__       =       weight
															lowerCamelCase__       =       weight





					def __str__( self	):
										lowerCamelCase__       =       ""
										for tail in self.adjacency:
															for head in self.adjacency[tail]:
																				lowerCamelCase__       =       self.adjacency[head][tail]
																				string += F"{head} -> {tail} == {weight}\n"
										return string.rstrip("\n"	)





					def 					__magic_name__ ( self	):
										lowerCamelCase__       =       []
										for tail in self.adjacency:
															for head in self.adjacency[tail]:
																				output.append((tail, head, self.adjacency[head][tail])	)
										return output





					def 					__magic_name__ ( self	):
										return self.adjacency.keys()





					@staticmethod
					def 					__magic_name__ ( _lowerCAmelCase=None	,  _lowerCAmelCase=None	):
										lowerCamelCase__       =       Graph()
										if vertices is None:
															lowerCamelCase__       =       []
										if edges is None:
															lowerCamelCase__       =       []
										for vertex in vertices:
															g.add_vertex(_lowerCAmelCase	)
										for edge in edges:
															g.add_edge(*_lowerCAmelCase	)
										return g

					class SCREAMING_SNAKE_CASE_ :





										"""simple docstring"""


										def __init__( self	):
															lowerCamelCase__       =       {}
															lowerCamelCase__       =       {}





										def __len__( self	):
															return len(self.parent	)





										def 					__magic_name__ ( self	,  _lowerCAmelCase	):
															if item in self.parent:
																				return self.find(_lowerCAmelCase	)

															lowerCamelCase__       =       item
															lowerCamelCase__       =       0
															return item





										def 					__magic_name__ ( self	,  _lowerCAmelCase	):
															if item not in self.parent:
																				return self.make_set(_lowerCAmelCase	)
															if item != self.parent[item]:
																				lowerCamelCase__       =       self.find(self.parent[item]	)
															return self.parent[item]






										def 					__magic_name__ ( self	,  _lowerCAmelCase	,  _lowerCAmelCase	):
															lowerCamelCase__       =       self.find(_lowerCAmelCase	)
															lowerCamelCase__       =       self.find(_lowerCAmelCase	)

															if roota == roota:
																				return roota

															if self.rank[roota] > self.rank[roota]:
																				lowerCamelCase__       =       roota
																				return roota

															if self.rank[roota] < self.rank[roota]:
																				lowerCamelCase__       =       roota
																				return roota

															if self.rank[roota] == self.rank[roota]:
																				self.rank[roota] += 1
																				lowerCamelCase__       =       roota
																				return roota
															return None





					@staticmethod
					def 					__magic_name__ ( _lowerCAmelCase	):
										lowerCamelCase__       =       graph.num_vertices

										lowerCamelCase__       =       Graph.UnionFind()
										lowerCamelCase__       =       []
										while num_components > 1:
															lowerCamelCase__       =       {}
															for vertex in graph.get_vertices():
																				lowerCamelCase__       =       -1

															lowerCamelCase__       =       graph.get_edges()
															for edge in edges:
																				lowerCamelCase__    ,		lowerCamelCase__    ,		lowerCamelCase__       =       edge
																				edges.remove((tail, head, weight)	)
															for edge in edges:
																				lowerCamelCase__    ,		lowerCamelCase__    ,		lowerCamelCase__       =       edge
																				lowerCamelCase__       =       union_find.find(_lowerCAmelCase	)
																				lowerCamelCase__       =       union_find.find(_lowerCAmelCase	)
																				if seta != seta:
																									if cheap_edge[seta] == -1 or cheap_edge[seta][2] > weight:
																														lowerCamelCase__       =       [head, tail, weight]

																									if cheap_edge[seta] == -1 or cheap_edge[seta][2] > weight:
																														lowerCamelCase__       =       [head, tail, weight]
															for vertex in cheap_edge:
																				if cheap_edge[vertex] != -1:
																									lowerCamelCase__    ,		lowerCamelCase__    ,		lowerCamelCase__       =       cheap_edge[vertex]
																									if union_find.find(_lowerCAmelCase	) != union_find.find(_lowerCAmelCase	):
																														union_find.union(_lowerCAmelCase	,  _lowerCAmelCase	)
																														mst_edges.append(cheap_edge[vertex]	)
																														lowerCamelCase__       =       num_components - 1
										lowerCamelCase__       =       Graph.build(edges=_lowerCAmelCase	)
										return mst








def    __UpperCamelCase      (    a) ->str:

					if isinstance(a,     a):
										raise TypeError("'float' object cannot be interpreted as an integer")
					if isinstance(a,     a):
										raise TypeError("'str' object cannot be interpreted as an integer")

					if num == 0:
										return "0b0"

					lowerCamelCase__       =       False

					if num < 0:
										lowerCamelCase__       =       True
										lowerCamelCase__       =       -num

					lowerCamelCase__       =       []
					while num > 0:
										binary.insert(0,     num % 2)
										num >>= 1

					if negative:
										return "-0b" + "".join(str(a) for e in binary)

					return "0b" + "".join(str(a) for e in binary)


if __name__ == "__main__":
						import doctest

						doctest.testmod()

