Question must use python   Task 04 (Cycle Finding): It was a very hectic day for Dora. Before going to sleep, Dora wants to find out if there is any cycle in the map of the city. Since Dora has traveled the whole country twice, she is feeling very exhausted and asks you to solve the problem. However, Dora has made the roads of the cities directed in her map, so that you don't get bored. In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. [Wikipedia] Input: The given map will be a directed and unweighted graph. The first line contains two integers \( N \) and \( M(1<=N, M<=100) \) - the number of cities and the total number of roads. The next \( M \) lines will contain two integers \( u_{i}, v_{i}\left(1<=u_{i}, v_{i}<=\right. \) N) - denoting there is a bidirectional road between \( u_{i} \) and \( v_{i} \). Output: Print "YES" if the map contains any CYcle, otherwise print "NO".

&#12304;General guidance&#12305;The answer provided below has been developed in a clear step by step manner.Step1/2Answer:-To detect a cycle in a directed graph, we can use the Depth-First Search (DFS) algorithm. We will perform a DFS on each unvisited node of the graph and while exploring the graph, if we encounter a node that is already visited, then there exists a cycle in the graph.Algorithm:Create a graph using the given inputs.Create a visited set to keep track of the visited nodes.For each unvisited node in the graph, perform a DFS.While performing the DFS, if a node is already visited, then there exists a cycle in the graph. Return "YES".If we have explored all the nodes and not found any cycle, then return "NO".Explanation:Please refer to solution in this step.Step2/2The complete python code along with comments is given below:# Define a function to check if a given node in a graph has a cycledef has_cycle(graph, node, visited, rec_stack): # Add the node to the visited set and the recursion stack visited.add(node) rec_stack.add(node) # Check each neighbor of the node for neighbor in graph[node]: # If the neighbor hasn't been visited yet, check if it has a cycle if neighbor not in visited: if has_cycle(graph, neighbor, visited, rec_stack): return True # If the neighbor is already in the recursion stack, there is a cycle elif neighbor in rec_stack: return True # Remove the node from the recursion stack and return False rec_stack.remove(node) return Falseprint("Enter the input: ")# Read in the number of cities (n) and roads (m)n, m = map(int, input().split())# Check that n and m are valid (i.e., between 1 and 100, incl ... See the full answer