




"""simple docstring"""







from collections import defaultdict




class       lowerCAmelCase__       :


				"""simple docstring"""





				def __init__(     self					:	Tuple    ,   lowercase__					:	Any    ,   lowercase__					:	int						):
						__lowercase				:		List[str]												=				total  # total no of tasks (N)

						# DP table will have a dimension of (2^M)*N
						# initially all values are set to -1
						__lowercase				:		Dict												=				[
						    [-1 for i in range(total + 1						)] for j in range(2 ** len(lowercase__						)						)
						]

						__lowercase				:		Optional[int]												=				defaultdict(lowercase__						)  # stores the list of persons for each task

						# final_mask is used to check if all persons are included by setting all bits
						# to 1
						__lowercase				:		int												=				(1 << len(lowercase__						)) - 1



				def       snake_case    (     self					:	Dict    ,   lowercase__					:	Optional[int]    ,   lowercase__					:	Union[str, Any]						):
						# if mask == self.finalmask all persons are distributed tasks, return 1
						if mask == self.final_mask:
								return 1

						# if not everyone gets the task and no more tasks are available, return 0
						if task_no > self.total_tasks:
								return 0

						# if case already considered
						if self.dp[mask][task_no] != -1:
								return self.dp[mask][task_no]

						# Number of ways when we don't this task in the arrangement
						__lowercase				:		Union[str, Any]												=				self.count_ways_until(lowercase__    ,   task_no + 1						)

						# now assign the tasks one by one to all possible persons and recursively
						# assign for the remaining tasks.
						if task_no in self.task:
								for p in self.task[task_no]:
										# if p is already given a task
										if mask & (1 << p):
												continue

										# assign this task to p and change the mask value. And recursively
										# assign tasks with the new mask value.
										total_ways_util += self.count_ways_until(mask | (1 << p)    ,   task_no + 1						)

        # save the value.
						__lowercase				:		Tuple												=				total_ways_util

						return self.dp[mask][task_no]



				def       snake_case    (     self					:	Dict    ,   lowercase__					:	Tuple						):
						# Store the list of persons for each task
						for i in range(len(lowercase__						)						):
								for j in task_performed[i]:
										self.task[j].append(lowercase__						)

        # call the function to fill the DP table, final answer is stored in dp[0][1]
						return self.count_ways_until(0    ,   1						)


if __name__ == "__main__":
						__A   :  Any					=      5  # total no of tasks (the value of N)

						# the list of tasks that can be done by M persons.
						__A   :  Tuple					=      [[1, 3, 4], [1, 2, 5], [3, 4]]
						print(
						    AssignmentUsingBitmask(task_performed, total_tasks).count_no_of_ways(
						        task_performed
						    )
						)






"""simple docstring"""







from __future__ import annotations

import os
from collections.abc import Mapping

__A   :  str					=      tuple[int, int]




class       lowerCAmelCase__       :


				"""simple docstring"""





				def __init__(     self					:	int    ,   lowercase__					:	set[int]    ,   lowercase__					:	Mapping[EdgeT, int]						):
						__lowercase				:		set[int]												=				vertices
						__lowercase				:		dict[EdgeT, int]												=				{
						    (min(lowercase__						), max(lowercase__						)): weight for edge, weight in edges.items()
						}



				def       snake_case    (     self					:	Optional[Any]    ,   lowercase__					:	EdgeT    ,   lowercase__					:	int						):
						self.vertices.add(edge[0]						)
						self.vertices.add(edge[1]						)
						__lowercase				:		Union[str, Any]												=				weight



				def       snake_case    (     self					:	Dict						):
						__lowercase				:		Graph												=				Graph({min(self.vertices						)}    ,   {}						)
						__lowercase				:		EdgeT
						__lowercase				:		int
						__lowercase				:		EdgeT
						__lowercase				:		int

						while len(subgraph.vertices						) < len(self.vertices						):
								__lowercase				:		int												=				max(self.edges.values()						) + 1
								for edge, weight in self.edges.items():
										if (edge[0] in subgraph.vertices) ^ (edge[1] in subgraph.vertices):
												if weight < min_weight:
														__lowercase				:		Optional[Any]												=				edge
														__lowercase				:		List[str]												=				weight

								subgraph.add_edge(lowercase__    ,   lowercase__						)

						return subgraph





def 						snake_case__       (					_lowerCamelCase = "p107_network.txt"				)			->int:






		"""simple docstring"""


		__lowercase				:		str												=				os.path.abspath(os.path.dirname(_lowerCamelCase				)				)
		__lowercase				:		str												=				os.path.join(_lowerCamelCase,  _lowerCamelCase				)
		__lowercase				:		dict[EdgeT, int]												=				{}
		__lowercase				:		list[str]
		__lowercase				:		int
		__lowercase				:		int

		with open(_lowerCamelCase				) as f:
				__lowercase				:		List[str]												=				f.read().strip().split("\n"				)

		__lowercase				:		Any												=				[line.split(","				) for line in data]

		for edgea in range(1,  len(_lowerCamelCase				)				):
				for edgea in range(_lowerCamelCase				):
						if adjaceny_matrix[edgea][edgea] != "-":
								__lowercase				:		Dict												=				int(adjaceny_matrix[edgea][edgea]				)

		__lowercase				:		Graph												=				Graph(set(range(len(_lowerCamelCase				)				)				),  _lowerCamelCase				)

		__lowercase				:		Graph												=				graph.prims_algorithm()

		__lowercase				:		int												=				sum(graph.edges.values()				)
		__lowercase				:		int												=				sum(subgraph.edges.values()				)

		return initial_total - optimal_total


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