





'''simple docstring'''

from collections import defaultdict

class       UpperCAmelCase :




		def __init__(self      :	Optional[Any]							,			A__      :	str							,			A__      :	Any				)					-> Tuple:
						lowercase         = total  # total no of tasks (N)

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

						lowercase         = defaultdict(A__				)  # 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         = (1 << len(A__				)) - 1




		def 				UpperCAmelCase__   (self      :	str							,			A__      :	Optional[int]							,			A__      :	Any				)					-> 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         = self.count_ways_until(A__							,			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         = total_ways_util

						return self.dp[mask][task_no]





		def 				UpperCAmelCase__   (self      :	Optional[int]							,			A__      :	List[str]				)					-> Any:
						# Store the list of persons for each task
						for i in range(len(A__				)				):
										for j in task_performed[i]:
														self.task[j].append(A__				)

        # 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__":
			__lowerCamelCase : str											=			5  # total no of tasks (the value of N)

			# the list of tasks that can be done by M persons.
			__lowerCamelCase : Any											=			[[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

from collections import deque
from collections.abc import Sequence
from dataclasses import dataclass
from typing import Any

@dataclass
class       UpperCAmelCase :
		UpperCAmelCase					:	int
		UpperCAmelCase					:	Node | None 			=		None
		UpperCAmelCase					:	Node | None 			=		None







def 							UpperCAmelCase_    (	):

				"""simple docstring"""






				lowercase         = Node(1							)
				lowercase         = Node(2							)
				lowercase         = Node(3							)
				lowercase         = Node(4							)
				lowercase         = Node(5							)
				return tree







def 							UpperCAmelCase_    (	lowerCAmelCase_							):

				"""simple docstring"""






				return [root.data, *preorder(root.left							), *preorder(root.right							)] if root else []







def 							UpperCAmelCase_    (	lowerCAmelCase_							):

				"""simple docstring"""






				return postorder(root.left							) + postorder(root.right							) + [root.data] if root else []







def 							UpperCAmelCase_    (	lowerCAmelCase_							):

				"""simple docstring"""






				return [*inorder(root.left							), root.data, *inorder(root.right							)] if root else []







def 							UpperCAmelCase_    (	lowerCAmelCase_							):

				"""simple docstring"""






				return (max(height(root.left							)		,							height(root.right							)							) + 1) if root else 0







def 							UpperCAmelCase_    (	lowerCAmelCase_							):

				"""simple docstring"""






				lowercase         = []

				if root is None:
								return output

				lowercase         = deque([root]							)

				while process_queue:
								lowercase         = process_queue.popleft()
								output.append(node.data							)

								if node.left:
												process_queue.append(node.left							)
								if node.right:
												process_queue.append(node.right							)
				return output







def 							UpperCAmelCase_    (	lowerCAmelCase_		,							lowerCAmelCase_							):

				"""simple docstring"""






				lowercase         = []

				def populate_output(lowerCAmelCase_		,							lowerCAmelCase_							) -> None:
								if not root:
												return
								if level == 1:
												output.append(root.data							)
								elif level > 1:
												populate_output(root.left		,							level - 1							)
												populate_output(root.right		,							level - 1							)

				populate_output(lowerCAmelCase_		,							lowerCAmelCase_							)
				return output







def 							UpperCAmelCase_    (	lowerCAmelCase_		,							lowerCAmelCase_							):

				"""simple docstring"""






				lowercase         = []

				def populate_output(lowerCAmelCase_		,							lowerCAmelCase_							) -> None:
								if root is None:
												return
								if level == 1:
												output.append(root.data							)
								elif level > 1:
												populate_output(root.right		,							level - 1							)
												populate_output(root.left		,							level - 1							)

				populate_output(lowerCAmelCase_		,							lowerCAmelCase_							)
				return output







def 							UpperCAmelCase_    (	lowerCAmelCase_							):

				"""simple docstring"""






				if root is None:
								return []

				lowercase         = []

				lowercase         = 0
				lowercase         = height(lowerCAmelCase_							)

				for h in range(1		,							height_tree + 1							):
								if not flag:
												output.append(get_nodes_from_left_to_right(lowerCAmelCase_		,							lowerCAmelCase_							)							)
												lowercase         = 1
								else:
												output.append(get_nodes_from_right_to_left(lowerCAmelCase_		,							lowerCAmelCase_							)							)
												lowercase         = 0

				return output







def 							UpperCAmelCase_    (	):  # Main function for testing.

				"""simple docstring"""






				lowercase         = make_tree()
				print(f'In-order Traversal: {inorder(lowerCAmelCase_							)}'							)
				print(f'Pre-order Traversal: {preorder(lowerCAmelCase_							)}'							)
				print(f'Post-order Traversal: {postorder(lowerCAmelCase_							)}'		,							"\n"							)

				print(f'Height of Tree: {height(lowerCAmelCase_							)}'		,							"\n"							)

				print("Complete Level Order Traversal: "							)
				print(level_order(lowerCAmelCase_							)		,							"\n"							)

				print("Level-wise order Traversal: "							)

				for level in range(1		,							height(lowerCAmelCase_							) + 1							):
								print(f'Level {level}:'		,							get_nodes_from_left_to_right(lowerCAmelCase_		,							level=lowerCAmelCase_							)							)

				print("\nZigZag order Traversal: "							)
				print(zigzag(lowerCAmelCase_							)							)


if __name__ == "__main__":
			import doctest

			doctest.testmod()
			main()




