




lowerCamelCase_  						=   [
    ["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	):
    SCREAMING_SNAKE_CASE__								=set()
    for row in edge_array:
        for item in row:
            distinct_edge.add(item[0]	)
    return list(__UpperCamelCase	)



def 	UpperCAmelCase_    (	__UpperCamelCase,				__UpperCamelCase	):
    SCREAMING_SNAKE_CASE__								=["""0"""] * len(__UpperCamelCase	)
    for i, row in enumerate(__UpperCamelCase	):
        for item in row:
            if distinct_edge in item[0]:
                SCREAMING_SNAKE_CASE__								="""1"""
                break
    return "".join(__UpperCamelCase	)



def 	UpperCAmelCase_    (	__UpperCamelCase	):
    SCREAMING_SNAKE_CASE__								=get_distinct_edge(__UpperCamelCase	)
    SCREAMING_SNAKE_CASE__								={}

    for item in distinct_edge:
        SCREAMING_SNAKE_CASE__								=get_bitcode(__UpperCamelCase,				__UpperCamelCase	)
        # print('bit',bit)
        # bt=''.join(bit)
        SCREAMING_SNAKE_CASE__								=bit.count("""1"""	)
        SCREAMING_SNAKE_CASE__								=[s, bit]
    # Store [Distinct edge, WT(Bitcode), Bitcode] in descending order
    SCREAMING_SNAKE_CASE__								=[
        [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	):
    SCREAMING_SNAKE_CASE__								={}
    for _, item in enumerate(__UpperCamelCase	):
        nodes.setdefault(item[2],				[]	).append(item[0]	)
    return nodes



def 	UpperCAmelCase_    (	__UpperCamelCase	):
    SCREAMING_SNAKE_CASE__								={}
    for key, value in nodes.items():
        SCREAMING_SNAKE_CASE__								=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]:
        SCREAMING_SNAKE_CASE__								=0
        SCREAMING_SNAKE_CASE__								=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:
                        SCREAMING_SNAKE_CASE__								=[nodes[j]]
                    count += 1
            if count == 0:
                SCREAMING_SNAKE_CASE__								=ca + 1
            else:
                break



def 	UpperCAmelCase_    (	__UpperCamelCase,				__UpperCamelCase	):
    SCREAMING_SNAKE_CASE__								=cluster[max(cluster.keys()	)]
    SCREAMING_SNAKE_CASE__								="""Header"""
    SCREAMING_SNAKE_CASE__								={}
    for i in x:
        if (["Header"],) in graph:
            graph[(["Header"],)].append(x[i]	)
        else:
            SCREAMING_SNAKE_CASE__								=[x[i]]
    for i in x:
        SCREAMING_SNAKE_CASE__								=[["""Header"""]]
    SCREAMING_SNAKE_CASE__								=1
    while i < max(__UpperCamelCase	) - 1:
        create_edge(__UpperCamelCase,				__UpperCamelCase,				__UpperCamelCase,				__UpperCamelCase	)
        SCREAMING_SNAKE_CASE__								=i + 1
    return graph



def 	UpperCAmelCase_    (	__UpperCamelCase,				__UpperCamelCase,				__UpperCamelCase,				__UpperCamelCase=None	):
    SCREAMING_SNAKE_CASE__								=(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	):
    SCREAMING_SNAKE_CASE__								=int(s / 100 * (len(__UpperCamelCase	) - 1)	)
    for i in cluster[k]:
        my_dfs(__UpperCamelCase,				tuple(cluster[k][i]	),				(["""Header"""],)	)



def 	UpperCAmelCase_    (	__UpperCamelCase	):
    SCREAMING_SNAKE_CASE__								=[]
    for edges in paths:
        SCREAMING_SNAKE_CASE__								=[]
        for j in range(len(__UpperCamelCase	) - 1	):
            SCREAMING_SNAKE_CASE__								=list(edges[j]	)
            for e in temp:
                SCREAMING_SNAKE_CASE__								=(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]	)	):
            SCREAMING_SNAKE_CASE__								=edge_array[i][j].split("""-"""	)
            SCREAMING_SNAKE_CASE__								=t


if __name__ == "__main__":
    preprocess(edge_array)
    lowerCamelCase_  						=   get_frequency_table(edge_array)
    lowerCamelCase_  						=   get_nodes(frequency_table)
    lowerCamelCase_  						=   get_cluster(nodes)
    lowerCamelCase_  						=   get_support(cluster)
    lowerCamelCase_  						=   construct_graph(cluster, nodes)
    find_freq_subgraph_given_support(60, cluster, graph)
    lowerCamelCase_  						=   []
    lowerCamelCase_  						=   freq_subgraphs_edge_list(paths)
    print_all()












def 	UpperCAmelCase_    (	__UpperCamelCase,				__UpperCamelCase	):
    SCREAMING_SNAKE_CASE__								=1.0
    for i in range(1,				r + 1	):
        ret *= (n + 1 - i) / i
    return round(__UpperCamelCase	)



def 	UpperCAmelCase_    (	__UpperCamelCase	):
    return choose(8 + n,				__UpperCamelCase	) + choose(9 + n,				__UpperCamelCase	) - 10



def 	UpperCAmelCase_    (	__UpperCamelCase	):
    return sum(non_bouncy_exact(__UpperCamelCase	) for i in range(1,				n + 1	)	)



def 	UpperCAmelCase_    (	__UpperCamelCase = 100	):
    return non_bouncy_upto(__UpperCamelCase	)


if __name__ == "__main__":
    print(f"""{solution() = }""")






