





'''simple docstring'''

lowerCAmelCase__	:					Optional[int]	     =       [
    ["ab-e1", "ac-e3", "ad-e5", "bc-e4", "bd-e2", "be-e6", "bh-e12", "cd-e2", "ce-e4",
     "de-e1", "df-e8", "dg-e5", "dh-e10", "ef-e3", "eg-e2", "fg-e6", "gh-e6", "hi-e3"],
    ["ab-e1", "ac-e3", "ad-e5", "bc-e4", "bd-e2", "be-e6", "cd-e2", "de-e1", "df-e8",
     "ef-e3", "eg-e2", "fg-e6"],
    ["ab-e1", "ac-e3", "bc-e4", "bd-e2", "de-e1", "df-e8", "dg-e5", "ef-e3", "eg-e2",
     "eh-e12", "fg-e6", "fh-e10", "gh-e6"],
    ["ab-e1", "ac-e3", "bc-e4", "bd-e2", "bh-e12", "cd-e2", "df-e8", "dh-e10"],
    ["ab-e1", "ac-e3", "ad-e5", "bc-e4", "bd-e2", "cd-e2", "ce-e4", "de-e1", "df-e8",
     "dg-e5", "ef-e3", "eg-e2", "fg-e6"]
]


def 		__UpperCamelCase		(       _UpperCAmelCase   ):
		__UpperCAmelCase     :				Union[str, Any]					   =			set()
		for row in edge_array:
				for item in row:
						distinct_edge.add(item[0]   )
		return list(_UpperCAmelCase   )


def 		__UpperCamelCase		(       _UpperCAmelCase,    _UpperCAmelCase   ):
		__UpperCAmelCase     :				Union[str, Any]					   =			["0"] * len(_UpperCAmelCase   )
		for i, row in enumerate(_UpperCAmelCase   ):
				for item in row:
						if distinct_edge in item[0]:
								__UpperCAmelCase     :				str					   =			"1"
								break
		return "".join(_UpperCAmelCase   )


def 		__UpperCamelCase		(       _UpperCAmelCase   ):
		__UpperCAmelCase     :				Tuple					   =			get_distinct_edge(_UpperCAmelCase   )
		__UpperCAmelCase     :				str					   =			{}

		for item in distinct_edge:
				__UpperCAmelCase     :				str					   =			get_bitcode(_UpperCAmelCase,    _UpperCAmelCase   )
				# print('bit',bit)
				# bt=''.join(bit)
				__UpperCAmelCase     :				Optional[int]					   =			bit.count("1"   )
				__UpperCAmelCase     :				Dict					   =			[s, bit]
		# Store [Distinct edge, WT(Bitcode), Bitcode] in descending order
		__UpperCAmelCase     :				str					   =			[
		    [k, v[0], v[1]]
		    for k, v in sorted(frequency_table.items(),    key=lambda _UpperCAmelCase   : v[1][0],    reverse=_UpperCAmelCase   )
		]
		return sorted_frequency_table


def 		__UpperCamelCase		(       _UpperCAmelCase   ):
		__UpperCAmelCase     :				Optional[int]					   =			{}
		for _, item in enumerate(_UpperCAmelCase   ):
				nodes.setdefault(item[2],    []   ).append(item[0]   )
		return nodes


def 		__UpperCamelCase		(       _UpperCAmelCase   ):
		__UpperCAmelCase     :				int					   =			{}
		for key, value in nodes.items():
				__UpperCAmelCase     :				str					   =			value
		return cluster


def 		__UpperCamelCase		(       _UpperCAmelCase   ):
		return [i * 100 / len(_UpperCAmelCase   ) for i in cluster]


def 		__UpperCamelCase		(       ):
		print("\nNodes\n"   )
		for key, value in nodes.items():
				print(_UpperCAmelCase,    _UpperCAmelCase   )
		print("\nSupport\n"   )
		print(_UpperCAmelCase   )
		print("\n Cluster \n"   )
		for key, value in sorted(cluster.items(),    reverse=_UpperCAmelCase   ):
				print(_UpperCAmelCase,    _UpperCAmelCase   )
		print("\n Graph\n"   )
		for key, value in graph.items():
				print(_UpperCAmelCase,    _UpperCAmelCase   )
		print("\n Edge List of Frequent subgraphs \n"   )
		for edge_list in freq_subgraph_edge_list:
				print(_UpperCAmelCase   )


def 		__UpperCamelCase		(       _UpperCAmelCase,    _UpperCAmelCase,    _UpperCAmelCase,    _UpperCAmelCase   ):

		for i in cluster[ca]:
				__UpperCAmelCase     :				Optional[int]					   =			0
				__UpperCAmelCase     :				Optional[int]					   =			ca + 1
				while ca < max(cluster.keys()   ):
						for j in cluster[ca]:
								if int(_UpperCAmelCase,    2   ) & int(_UpperCAmelCase,    2   ) == int(_UpperCAmelCase,    2   ):
										if tuple(nodes[i]   ) in graph:
												graph[tuple(nodes[i]   )].append(nodes[j]   )
										else:
												__UpperCAmelCase     :				Any					   =			[nodes[j]]
										count += 1
						if count == 0:
								__UpperCAmelCase     :				Dict					   =			ca + 1
						else:
								break


def 		__UpperCamelCase		(       _UpperCAmelCase,    _UpperCAmelCase   ):
		__UpperCAmelCase     :				Optional[Any]					   =			cluster[max(cluster.keys()   )]
		__UpperCAmelCase     :				Any					   =			"Header"
		__UpperCAmelCase     :				Union[str, Any]					   =			{}
		for i in x:
				if (["Header"],) in graph:
						graph[(["Header"],)].append(x[i]   )
				else:
						__UpperCAmelCase     :				Any					   =			[x[i]]
		for i in x:
				__UpperCAmelCase     :				str					   =			[["Header"]]
		__UpperCAmelCase     :				Tuple					   =			1
		while i < max(_UpperCAmelCase   ) - 1:
				create_edge(_UpperCAmelCase,    _UpperCAmelCase,    _UpperCAmelCase,    _UpperCAmelCase   )
				__UpperCAmelCase     :				str					   =			i + 1
		return graph


def 		__UpperCamelCase		(       _UpperCAmelCase,    _UpperCAmelCase,    _UpperCAmelCase,    _UpperCAmelCase=None   ):
		__UpperCAmelCase     :				Optional[int]					   =			(path or []) + [start]
		if start == end:
				paths.append(_UpperCAmelCase   )
		for node in graph[start]:
				if tuple(_UpperCAmelCase   ) not in path:
						my_dfs(_UpperCAmelCase,    tuple(_UpperCAmelCase   ),    _UpperCAmelCase,    _UpperCAmelCase   )


def 		__UpperCamelCase		(       _UpperCAmelCase,    _UpperCAmelCase,    _UpperCAmelCase   ):
		__UpperCAmelCase     :				Optional[int]					   =			int(s / 100 * (len(_UpperCAmelCase   ) - 1)   )
		for i in cluster[k]:
				my_dfs(_UpperCAmelCase,    tuple(cluster[k][i]   ),    (["Header"],)   )


def 		__UpperCamelCase		(       _UpperCAmelCase   ):
		__UpperCAmelCase     :				Any					   =			[]
		for edges in paths:
				__UpperCAmelCase     :				Union[str, Any]					   =			[]
				for j in range(len(_UpperCAmelCase   ) - 1   ):
						__UpperCAmelCase     :				str					   =			list(edges[j]   )
						for e in temp:
								__UpperCAmelCase     :				List[Any]					   =			(e[0], e[1])
								el.append(_UpperCAmelCase   )
				freq_sub_el.append(_UpperCAmelCase   )
		return freq_sub_el


def 		__UpperCamelCase		(       _UpperCAmelCase   ):

		for i in range(len(_UpperCAmelCase   )   ):
				for j in range(len(edge_array[i]   )   ):
						__UpperCAmelCase     :				str					   =			edge_array[i][j].split("-"   )
						__UpperCAmelCase     :				Union[str, Any]					   =			t


if __name__ == "__main__":
			preprocess(edge_array)
			lowerCAmelCase__	:					Union[str, Any]	     =       get_frequency_table(edge_array)
			lowerCAmelCase__	:					Union[str, Any]	     =       get_nodes(frequency_table)
			lowerCAmelCase__	:					int	     =       get_cluster(nodes)
			lowerCAmelCase__	:					str	     =       get_support(cluster)
			lowerCAmelCase__	:					List[str]	     =       construct_graph(cluster, nodes)
			find_freq_subgraph_given_support(60, cluster, graph)
			lowerCAmelCase__	:					Union[str, Any]	     =       []
			lowerCAmelCase__	:					Tuple	     =       freq_subgraphs_edge_list(paths)
			print_all()








class lowerCAmelCase_						:

 '''simple docstring'''

 def __init__(	self		,      _UpperCAmelCase					):
       snake_case_       =      val
       # Number of nodes in left subtree
       snake_case_       =      0
       snake_case_       =      None
       snake_case_       =      None
       snake_case_       =      None





 def 						UpperCamelCase__     (	self		,      _UpperCAmelCase					):
       assert self.left_tree_size == other.left_tree_size, "Unequal Sizes of Blocks"

       if self.val < other.val:
             snake_case_       =      self.right
             snake_case_       =      None
             if self.right:
                   snake_case_       =      other
             snake_case_       =      other
             snake_case_       =      self.left_tree_size * 2 + 1
             return self
       else:
             snake_case_       =      other.right
             snake_case_       =      None
             if other.right:
                   snake_case_       =      self
             snake_case_       =      self
             snake_case_       =      other.left_tree_size * 2 + 1
             return other







class lowerCAmelCase_						:

 '''simple docstring'''

 def __init__(	self		,      _UpperCAmelCase=None		,      _UpperCAmelCase=None		,      _UpperCAmelCase=0					):
       snake_case_       =      heap_size
       snake_case_       =      bottom_root
       snake_case_       =      min_node



 def 						UpperCamelCase__     (	self		,      _UpperCAmelCase					):

       # Empty heaps corner cases
       if other.size == 0:
             return None
       if self.size == 0:
             snake_case_       =      other.size
             snake_case_       =      other.bottom_root
             snake_case_       =      other.min_node
             return None
       # Update size
       snake_case_       =      self.size + other.size

       # Update min.node
       if self.min_node.val > other.min_node.val:
             snake_case_       =      other.min_node
       # Merge

       # Order roots by left_subtree_size
       snake_case_       =      []
       snake_case_       ,    snake_case_       =      self.bottom_root, other.bottom_root
       while i or j:
             if i and ((not j) or i.left_tree_size < j.left_tree_size):
                   combined_roots_list.append((i, True)					)
                   snake_case_       =      i.parent
             else:
                   combined_roots_list.append((j, False)					)
                   snake_case_       =      j.parent
        # Insert links between them
       for i in range(len(_UpperCAmelCase					) - 1					):
             if combined_roots_list[i][1] != combined_roots_list[i + 1][1]:
                   snake_case_       =      combined_roots_list[i + 1][0]
                   snake_case_       =      combined_roots_list[i][0]
        # Consecutively merge roots with same left_tree_size
       snake_case_       =      combined_roots_list[0][0]
       while i.parent:
             if (
                 (i.left_tree_size == i.parent.left_tree_size) and (not i.parent.parent)
             ) or (
                 i.left_tree_size == i.parent.left_tree_size
                 and i.left_tree_size != i.parent.parent.left_tree_size
             ):
                   # Neighbouring Nodes
                   snake_case_       =      i.left
                   snake_case_       =      i.parent.parent

                   # Merging trees
                   snake_case_       =      i.merge_trees(i.parent					)

                   # Updating links
                   snake_case_       =      previous_node
                   snake_case_       =      next_node
                   if previous_node:
                         snake_case_       =      i
                   if next_node:
                         snake_case_       =      i
             else:
                   snake_case_       =      i.parent
        # Updating self.bottom_root
       while i.left:
             snake_case_       =      i.left
       snake_case_       =      i

       # Update other
       snake_case_       =      self.size
       snake_case_       =      self.bottom_root
       snake_case_       =      self.min_node

       # Return the merged heap
       return self



 def 						UpperCamelCase__     (	self		,      _UpperCAmelCase					):
       if self.size == 0:
             snake_case_       =      Node(_UpperCAmelCase					)
             snake_case_       =      1
             snake_case_       =      self.bottom_root
       else:
             # Create new node
             snake_case_       =      Node(_UpperCAmelCase					)

             # Update size
             self.size += 1

             # update min_node
             if val < self.min_node.val:
                   snake_case_       =      new_node
             # Put new_node as a bottom_root in heap
             snake_case_       =      new_node
             snake_case_       =      self.bottom_root
             snake_case_       =      new_node

             # Consecutively merge roots with same left_tree_size
             while (
                 self.bottom_root.parent
                 and self.bottom_root.left_tree_size
                 == self.bottom_root.parent.left_tree_size
             ):
                   # Next node
                   snake_case_       =      self.bottom_root.parent.parent

                   # Merge
                   snake_case_       =      self.bottom_root.merge_trees(self.bottom_root.parent					)

                   # Update Links
                   snake_case_       =      next_node
                   snake_case_       =      None
                   if next_node:
                         snake_case_       =      self.bottom_root



 def 						UpperCamelCase__     (	self					):
       return self.min_node.val



 def 						UpperCamelCase__     (	self					):
       return self.size == 0



 def 						UpperCamelCase__     (	self					):
       snake_case_       =      self.min_node.val

       # Last element in heap corner case
       if self.size == 1:
             # Update size
             snake_case_       =      0

             # Update bottom root
             snake_case_       =      None

             # Update min_node
             snake_case_       =      None

             return min_value
       # No right subtree corner case
       # The structure of the tree implies that this should be the bottom root
       # and there is at least one other root
       if self.min_node.right is None:
             # Update size
             self.size -= 1

             # Update bottom root
             snake_case_       =      self.bottom_root.parent
             snake_case_       =      None

             # Update min_node
             snake_case_       =      self.bottom_root
             snake_case_       =      self.bottom_root.parent
             while i:
                   if i.val < self.min_node.val:
                         snake_case_       =      i
                   snake_case_       =      i.parent
             return min_value
       # General case
       # Find the BinomialHeap of the right subtree of min_node
       snake_case_       =      self.min_node.right
       snake_case_       =      None
       snake_case_       =      bottom_of_new
       snake_case_       =      1

       # Size, min_node and bottom_root
       while bottom_of_new.left:
             snake_case_       =      size_of_new * 2 + 1
             snake_case_       =      bottom_of_new.left
             if bottom_of_new.val < min_of_new.val:
                   snake_case_       =      bottom_of_new
        # Corner case of single root on top left path
       if (not self.min_node.left) and (not self.min_node.parent):
             snake_case_       =      size_of_new
             snake_case_       =      bottom_of_new
             snake_case_       =      min_of_new
             # print("Single root, multiple nodes case")
             return min_value
       # Remaining cases
       # Construct heap of right subtree
       snake_case_       =      BinomialHeap(
           bottom_root=_UpperCAmelCase		,      min_node=_UpperCAmelCase		,      heap_size=_UpperCAmelCase					)

       # Update size
       snake_case_       =      self.size - 1 - size_of_new

       # Neighbour nodes
       snake_case_       =      self.min_node.left
       snake_case_       =      self.min_node.parent

       # Initialize new bottom_root and min_node
       snake_case_       =      previous_node or next_node
       snake_case_       =      next_node

       # Update links of previous_node and search below for new min_node and
       # bottom_root
       if previous_node:
             snake_case_       =      next_node

             # Update bottom_root and search for min_node below
             snake_case_       =      previous_node
             snake_case_       =      previous_node
             while self.bottom_root.left:
                   snake_case_       =      self.bottom_root.left
                   if self.bottom_root.val < self.min_node.val:
                         snake_case_       =      self.bottom_root
       if next_node:
             snake_case_       =      previous_node

             # Search for new min_node above min_node
             snake_case_       =      next_node
             while i:
                   if i.val < self.min_node.val:
                         snake_case_       =      i
                   snake_case_       =      i.parent
        # Merge heaps
       self.merge_heaps(_UpperCAmelCase					)

       return min_value



 def 						UpperCamelCase__     (	self					):
       snake_case_       =      self.bottom_root
       while top_root.parent:
             snake_case_       =      top_root.parent
       # preorder
       snake_case_       =      []
       self.__traversal(_UpperCAmelCase		,      _UpperCAmelCase					)
       return heap_pre_order



 def 						UpperCamelCase__     (	self		,      _UpperCAmelCase		,      _UpperCAmelCase		,      _UpperCAmelCase=0					):
       if curr_node:
             preorder.append((curr_node.val, level)					)
             self.__traversal(curr_node.left		,      _UpperCAmelCase		,      level + 1					)
             self.__traversal(curr_node.right		,      _UpperCAmelCase		,      level + 1					)
       else:
             preorder.append(('''#''', level)					)





 def __str__(	self					):
       if self.is_empty():
             return ""
       snake_case_       =      self.pre_order()

       return "\n".join(('''-''' * level + str(_UpperCAmelCase					)) for value, level in preorder_heap					)


# Unit Tests
if __name__ == "__main__":
   import doctest

   doctest.testmod()