<p>You are given an integer <code>n</code>, which indicates that there are <code>n</code> courses labeled from <code>1</code> to <code>n</code>. You are also given an array <code>relations</code> where <code>relations[i] = [prevCourse<sub>i</sub>, nextCourse<sub>i</sub>]</code>, representing a prerequisite relationship between course <code>prevCourse<sub>i</sub></code> and course <code>nextCourse<sub>i</sub></code>: course <code>prevCourse<sub>i</sub></code> has to be taken before course <code>nextCourse<sub>i</sub></code>. Also, you are given the integer <code>k</code>.</p>

<p>In one semester, you can take <strong>at most</strong> <code>k</code> courses as long as you have taken all the prerequisites in the <strong>previous</strong> semesters for the courses you are taking.</p>

<p>Return <em>the <strong>minimum</strong> number of semesters needed to take all courses</em>. The testcases will be generated such that it is possible to take every course.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/05/22/leetcode_parallel_courses_1.png" style="width: 269px; height: 147px;" />
<pre>
<strong>Input:</strong> n = 4, relations = [[2,1],[3,1],[1,4]], k = 2
<strong>Output:</strong> 3
<strong>Explanation:</strong> The figure above represents the given graph.
In the first semester, you can take courses 2 and 3.
In the second semester, you can take course 1.
In the third semester, you can take course 4.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/05/22/leetcode_parallel_courses_2.png" style="width: 271px; height: 211px;" />
<pre>
<strong>Input:</strong> n = 5, relations = [[2,1],[3,1],[4,1],[1,5]], k = 2
<strong>Output:</strong> 4
<strong>Explanation:</strong> The figure above represents the given graph.
In the first semester, you can only take courses 2 and 3 since you cannot take more than two per semester.
In the second semester, you can take course 4.
In the third semester, you can take course 1.
In the fourth semester, you can take course 5.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 15</code></li>
	<li><code>1 &lt;= k &lt;= n</code></li>
	<li><code>0 &lt;= relations.length &lt;= n * (n-1) / 2</code></li>
	<li><code>relations[i].length == 2</code></li>
	<li><code>1 &lt;= prevCourse<sub>i</sub>, nextCourse<sub>i</sub> &lt;= n</code></li>
	<li><code>prevCourse<sub>i</sub> != nextCourse<sub>i</sub></code></li>
	<li>All the pairs <code>[prevCourse<sub>i</sub>, nextCourse<sub>i</sub>]</code> are <strong>unique</strong>.</li>
	<li>The given graph is a directed acyclic graph.</li>
</ul>

class Solution:
    def __init__(self) : 
        self.graph = []
        self.out_degree = []
        self.in_degree = []
        self.bit_shifted_courses = []
        self.queue = collections.deque()
        self.seen = []
        self.start = 0
        self.goal  = 1
        self.limit = 1
        self.number_of_courses = 0
        self.max_semesters = 1 

    def set_up(self, n, relations, k) : 
        # graph size and out degree for n nodes 
        self.number_of_courses = n
        self.graph      = [0]*n 
        self.out_degree = [0]*n
        self.in_degree  = [0]*n
        # seen is 2 ^ n combinations of bit shifts 
        self.seen = [0] * (2**n)
        # goal is getting all of them 
        self.goal = 2**n-1
        # bit shifted courses for all unique bit identity of courses 
        self.bit_shifted_courses = [1<<c_i for c_i in range(n)]
        # off by one indexing 
        for prerequisite, post in relations : 
            self.graph[post-1] += 1 << (prerequisite - 1)
            self.out_degree[prerequisite - 1] += 1
            self.in_degree[post-1] += 1  
        # starting point and limit factor 
        self.queue.append((self.start, 0))
        self.limit = k

    def qualified_to_take_course(self, record_key, course_id) : 
        # if record key & self.graph[course_id] == self.graph[course_id] we have all prerequisites needed
        return record_key & self.graph[course_id] == self.graph[course_id]

    def have_not_taken_course(self, record_key, course_id) : 
        # if record_key & bit shifted course at course id is 0, we have not taken it 
        return record_key & self.bit_shifted_courses[course_id] == 0 

    def get_available_courses(self, record_key) : 
        # using record key 
        available = []
        # loop over number of courses 
        for course_id in range(self.number_of_courses) : 
            # if we have not taken it and can take it, add it 
            if self.have_not_taken_course(record_key, course_id) and self.qualified_to_take_course(record_key, course_id) : 
                available.append(course_id)
        # return when done 
        return available

    def get_prerequisites_in_available_courses(self, available) : 
        # return those that lead to other courses 
        # sort by out degree in increasing fashion, so that we consider pre-reqs in order of maximal coverage 
        available.sort(key = lambda course_id : self.out_degree[course_id], reverse=True)
        return [self.bit_shifted_courses[course_id] for course_id in available]

    def get_terminal_courses_in_available_courses(self, available) : 
        # return those that do not lead to other courses 
        # sort by in degree that have minimal requirements 
        available.sort(key = lambda course_id : self.in_degree[course_id])
        return [self.bit_shifted_courses[course_id] for course_id in available]

    def process_pre_reqs_and_terminals(self, pre_reqs, terminals, record_key, semesters) :
        # get new record key as combination of pre reqs and terminals we qualify for 
        record_key += sum(pre_reqs) + sum(terminals[:self.limit - len(pre_reqs)])
        # if record key is goal increment steps and return 
        if record_key == self.goal : 
            return semesters + 1 
        # otherwise, if we have not considered this combination yet 
        if self.seen[record_key] == 0 : 
            # consider it and mark it considered 
            self.queue.append((record_key, semesters+1))
            self.seen[record_key] = 1 
        # return 0 if not goal
        return 0  

    def process_pre_req_combinations(self, pre_reqs, record_key, semesters) : 
        # try all combinations 
        for combination in itertools.combinations(pre_reqs, self.limit) : 
            # getting the new pre reqs course bits 
            pre_reqs_key = sum(combination)
            # and updating record key 
            new_record_key = record_key + pre_reqs_key
            # if that completed what we needed 
            if new_record_key == self.goal : 
                # return steps plus 1 
                return semesters + 1 
            # otherwise, if we have not considered it 
            if self.seen[new_record_key] == 0 : 
                # consider it and mark as such 
                self.queue.append((new_record_key, semesters+1))
                self.seen[new_record_key] = 1 
        # return 0 by default if we never returned otherwise 
        return 0 

    def process_queue(self) : 
        # process queue and return result when found 
        while self.queue : 
            # pop from front
            record_key, semesters = self.queue.popleft()
            # insurance incase of other mishaps 
            self.max_semesters = max(self.max_semesters, semesters)
            # get available, pre_reqs, and terminals 
            available = self.get_available_courses(record_key) 
            pre_reqs  = self.get_prerequisites_in_available_courses([course_id for course_id in available if self.out_degree[course_id]])
            terminals = self.get_terminal_courses_in_available_courses([course_id for course_id in available if self.out_degree[course_id]==0])
            # if length of prereqs is at or under limit for semester 
            if len(pre_reqs) <= self.limit : 
                # get result of processing pre reqs and terminals 
                result = self.process_pre_reqs_and_terminals(pre_reqs, terminals, record_key, semesters)
                # if we got a finish result 
                if result != 0 : 
                    # return it 
                    return result 
            else : 
                # similar to above, but now we have too many prerequisites 
                result = self.process_pre_req_combinations(pre_reqs, record_key, semesters)
                # if we finish on account of this, return it 
                if result != 0 : 
                    return result 
        return self.max_semesters + 1 

    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:
        self.set_up(n, relations, k)
        return self.process_queue()
17000