Problem of the day
Let‘N’ = 3 , ‘K’ = 1 and ‘DEPENDENCIES’ = [ [1, 2] [2, 3] ].
In this example, if you want to take ‘COURSE_3’ then first you have to take ‘COURSE_2’ in the previous semester. If you want to take ‘COURSE_2’, then first you have to take ‘COURSE_1’ in the previous semester.
The value of ‘K’ is 1 which means in a semester we can choose at most 1 course.
The first line of input contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases follow.
The first line of each test case contains three single space-separated integers ‘N’,‘M’ and ‘K’ represent the number of courses, number of dependencies and maximum courses that you can take in one semester respectively.
The next ‘N’ line of each test case contains two single space-separated integers ‘X’ and ‘Y’ representing that the course ‘X’ must be taken before the course ‘Y’.
For each test case, print the minimum number of semesters required to take all the courses.
Print the output of each test case in a separate line.
You do not need to print anything; it has already been taken care of. Just implement the given function.
1 <= ‘T’ <= 10
1 <= ‘N’ <= 15
0 <= ‘M’ <= ‘N’ * (‘N’ - 1)/2
1 <= ‘X’, ‘Y’ and ‘K’ <= ‘N’
Time Limit: 1 second
2
4 3 2
2 1
3 1
1 4
5 0 2
3
3
For sample test case 1:
In the first semester we can choose ‘COURSE_2’ and ‘COURSE_3’ as these are not dependent on other courses. The value of ‘K’ is 2 which means in a semester we can choose at most 2 courses. So in the first semester, we choose these two courses.
After that in the second semester:
In the second semester, we can choose only the ‘COURSE_1’ as this course is not dependent on other courses. So in the first semester, we choose only one course.
After that in the third semester:
In the third semester, only one course is left i.e ‘COURSE_4’.So in the third semester, we choose the last course.
So, the minimum number of semesters required to take all the courses is 3.
For sample test case 2:
In this sample test case, no course is dependent on each other i.e all courses are independent. The value of ‘K’ is 2 which means in a semester we can choose at most 2 courses.
So in the first semester, we choose ‘COURSE_1’ and ‘COURSE_2’.
In the second semester, we choose ‘COURSE_3’ and ‘COURSE_4’.
In the third semester, we choose the last course i.e. ‘COURSE_5’.
So, the minimum number of semesters required to take all the courses is 3.
1
5 4 2
2 1
3 1
4 1
1 5
4
For sample test case 1:
In the first semester, we can choose ‘COURSE_2’, ‘COURSE_3’ and ‘COURSE_4’ as these are not dependent on other courses. The value of ‘K’ is 2 which means in a semester we can choose at most 2 courses. So in the first semester, let us assume we choose ‘COURSE_2’ and ‘COURSE_3’.
After the first semester:
In the second semester, we can choose only the ‘COURSE_4’ as this course is not dependent on other courses. So in the second semester, we choose only one course.
After that in the second semester:
In the third semester, we can choose only the ‘COURSE_1’ as this course is not dependent on other courses. So in the third semester, we choose only one course.
After that in the third semester:
In the fourth semester, only one course is left i.e ‘COURSE_5’.So in the fourth semester, we choose the last course.
So, the minimum number of semesters required to take all the courses is 4.