
from collections import deque




class     _SCREAMING_SNAKE_CASE     :



	def __init__(    self						,  lowercase						,  lowercase						,  lowercase )				->       None:
					lowerCamelCase_						=			process_name  # process name
					lowerCamelCase_						=			arrival_time  # arrival time of the process
					# completion time of finished process or last interrupted time
					lowerCamelCase_						=			arrival_time
					lowerCamelCase_						=			burst_time  # remaining burst time
					lowerCamelCase_						=			0  # total time of the process wait in ready queue
					lowerCamelCase_						=			0  # time from arrival time to completion time




class     _SCREAMING_SNAKE_CASE     :



	def __init__(    self						,  lowercase						,  lowercase						,  lowercase						,  lowercase						,  )				->       None:
					# total number of mlfq's queues
					lowerCamelCase_						=			number_of_queues
					# time slice of queues that round robin algorithm applied
					lowerCamelCase_						=			time_slices
					# unfinished process is in this ready_queue
					lowerCamelCase_						=			queue
					# current time
					lowerCamelCase_						=			current_time
					# finished process is in this sequence queue
					lowerCamelCase_						=			deque()



	def     SCREAMING_SNAKE_CASE_(    self )				->       list[str]:
					lowerCamelCase_						=			[]
					for i in range(len(self.finish_queue ) ):
									sequence.append(self.finish_queue[i].process_name )
					return sequence



	def     SCREAMING_SNAKE_CASE_(    self						,  lowercase )				->       list[int]:
					lowerCamelCase_						=			[]
					for i in range(len(lowercase ) ):
									waiting_times.append(queue[i].waiting_time )
					return waiting_times



	def     SCREAMING_SNAKE_CASE_(    self						,  lowercase )				->       list[int]:
					lowerCamelCase_						=			[]
					for i in range(len(lowercase ) ):
									turnaround_times.append(queue[i].turnaround_time )
					return turnaround_times



	def     SCREAMING_SNAKE_CASE_(    self						,  lowercase )				->       list[int]:
					lowerCamelCase_						=			[]
					for i in range(len(lowercase ) ):
									completion_times.append(queue[i].stop_time )
					return completion_times



	def     SCREAMING_SNAKE_CASE_(    self						,  lowercase )				->       list[int]:
					return [q.burst_time for q in queue]



	def     SCREAMING_SNAKE_CASE_(    self						,  lowercase )				->       int:
					process.waiting_time += self.current_time - process.stop_time
					return process.waiting_time



	def     SCREAMING_SNAKE_CASE_(    self						,  lowercase )				->       deque[Process]:
					lowerCamelCase_						=			deque()  # sequence deque of finished process
					while len(lowercase ) != 0:
									lowerCamelCase_						=			ready_queue.popleft()  # current process

									# if process's arrival time is later than current time, update current time
									if self.current_time < cp.arrival_time:
													self.current_time += cp.arrival_time

									# update waiting time of current process
									self.update_waiting_time(lowercase )
									# update current time
									self.current_time += cp.burst_time
									# finish the process and set the process's burst-time 0
									lowerCamelCase_						=			0
									# set the process's turnaround time because it is finished
									lowerCamelCase_						=			self.current_time - cp.arrival_time
									# set the completion time
									lowerCamelCase_						=			self.current_time
									# add the process to queue that has finished queue
									finished.append(lowercase )

					self.finish_queue.extend(lowercase )  # add finished process to finish queue
					# FCFS will finish all remaining processes
					return finished



	def     SCREAMING_SNAKE_CASE_(    self						,  lowercase						,  lowercase )				->       tuple[deque[Process], deque[Process]]:
					lowerCamelCase_						=			deque()  # sequence deque of terminated process
					# just for 1 cycle and unfinished processes will go back to queue
					for _ in range(len(lowercase ) ):
									lowerCamelCase_						=			ready_queue.popleft()  # current process

									# if process's arrival time is later than current time, update current time
									if self.current_time < cp.arrival_time:
													self.current_time += cp.arrival_time

									# update waiting time of unfinished processes
									self.update_waiting_time(lowercase )
									# if the burst time of process is bigger than time-slice
									if cp.burst_time > time_slice:
													# use CPU for only time-slice
													self.current_time += time_slice
													# update remaining burst time
													cp.burst_time -= time_slice
													# update end point time
													lowerCamelCase_						=			self.current_time
													# locate the process behind the queue because it is not finished
													ready_queue.append(lowercase )
									else:
													# use CPU for remaining burst time
													self.current_time += cp.burst_time
													# set burst time 0 because the process is finished
													lowerCamelCase_						=			0
													# set the finish time
													lowerCamelCase_						=			self.current_time
													# update the process' turnaround time because it is finished
													lowerCamelCase_						=			self.current_time - cp.arrival_time
													# add the process to queue that has finished queue
													finished.append(lowercase )

					self.finish_queue.extend(lowercase )  # add finished process to finish queue
					# return finished processes queue and remaining processes queue
					return finished, ready_queue



	def     SCREAMING_SNAKE_CASE_(    self )				->       deque[Process]:

					#  all queues except last one have round_robin algorithm
					for i in range(self.number_of_queues - 1 ):
									lowerCamelCase_	,    lowerCamelCase_						=			self.round_robin(
									    self.ready_queue						,  self.time_slices[i] )
					#  the last queue has first_come_first_served algorithm
					self.first_come_first_served(self.ready_queue )

					return self.finish_queue


if __name__ == "__main__":
			import doctest

			__A				=Process('''P1''', 0, 5_3)
			__A				=Process('''P2''', 0, 1_7)
			__A				=Process('''P3''', 0, 6_8)
			__A				=Process('''P4''', 0, 2_4)
			__A				=3
			__A				=[1_7, 2_5]
			__A				=deque([Pa, Pa, Pa, Pa])

			if len(time_slices) != number_of_queues - 1:
						raise SystemExit(0)

			doctest.testmod(extraglobs={'''queue''': deque([Pa, Pa, Pa, Pa])})

			__A				=Process('''P1''', 0, 5_3)
			__A				=Process('''P2''', 0, 1_7)
			__A				=Process('''P3''', 0, 6_8)
			__A				=Process('''P4''', 0, 2_4)
			__A				=3
			__A				=[1_7, 2_5]
			__A				=deque([Pa, Pa, Pa, Pa])
			__A				=MLFQ(number_of_queues, time_slices, queue, 0)
			__A				=mlfq.multi_level_feedback_queue()

			# print total waiting times of processes(P1, P2, P3, P4)
			print(
			    F"""waiting time:\
        \t\t\t{MLFQ.calculate_waiting_time(mlfq, [Pa, Pa, Pa, Pa])}"""
			)
			# print completion times of processes(P1, P2, P3, P4)
			print(
			    F"""completion time:\
        \t\t{MLFQ.calculate_completion_time(mlfq, [Pa, Pa, Pa, Pa])}"""
			)
			# print total turnaround times of processes(P1, P2, P3, P4)
			print(
			    F"""turnaround time:\
        \t\t{MLFQ.calculate_turnaround_time(mlfq, [Pa, Pa, Pa, Pa])}"""
			)
			# print sequence of finished processes
			print(
			    F"""sequence of finished processes:\
        {mlfq.calculate_sequence_of_finish_queue()}"""
			)




from collections import deque





def 			lowerCamelCase_ (				lowerCamelCase__    ):
				lowerCamelCase_						=			len(lowerCamelCase__    )
				lowerCamelCase_						=			deque()
				lowerCamelCase_						=			[False for _ in range(lowerCamelCase__    )]
				lowerCamelCase_						=			[-1 for _ in range(lowerCamelCase__    )]
				lowerCamelCase_						=			index_of[:]

				def strong_connect(lowerCamelCase__	, lowerCamelCase__	, lowerCamelCase__    ):
								lowerCamelCase_						=			index  # the number when this node is seen
								lowerCamelCase_						=			index  # lowest rank node reachable from here
								index += 1
								stack.append(lowerCamelCase__    )
								lowerCamelCase_						=			True

								for w in g[v]:
												if index_of[w] == -1:
																lowerCamelCase_						=			strong_connect(lowerCamelCase__	, lowerCamelCase__	, lowerCamelCase__    )
																lowerCamelCase_						=			(
																    lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v]
																)
												elif on_stack[w]:
																lowerCamelCase_						=			(
																    lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v]
																)

								if lowlink_of[v] == index_of[v]:
												lowerCamelCase_						=			[]
												lowerCamelCase_						=			stack.pop()
												lowerCamelCase_						=			False
												component.append(lowerCamelCase__    )
												while w != v:
																lowerCamelCase_						=			stack.pop()
																lowerCamelCase_						=			False
																component.append(lowerCamelCase__    )
												components.append(lowerCamelCase__    )
								return index

				lowerCamelCase_						=			[]
				for v in range(lowerCamelCase__    ):
								if index_of[v] == -1:
												strong_connect(lowerCamelCase__	, 0	, lowerCamelCase__    )

				return components





def 			lowerCamelCase_ (				lowerCamelCase__	, lowerCamelCase__    ):
				lowerCamelCase_						=			[[] for _ in range(lowerCamelCase__    )]
				for u, v in edges:
								g[u].append(lowerCamelCase__    )
				return g


if __name__ == "__main__":
			# Test
			__A				=7
			__A				=[0, 0, 1, 2, 3, 3, 4, 4, 6]
			__A				=[1, 3, 2, 0, 1, 4, 5, 6, 5]
			__A				=[(u, v) for u, v in zip(source, target)]
			__A				=create_graph(n_vertices, edges)

			assert [[5], [6], [4], [3, 2, 1, 0]] == tarjan(g)


