answer:from collections import defaultdict, deque def find_switch_order(test_cases): def topological_sort(N, graph, in_degree): queue = deque() result = [] # Initialize queue with nodes having in-degree 0 for i in range(1, N + 1): if in_degree[i] == 0: queue.append(i) while queue: node = queue.popleft() result.append(node) for neighbor in graph[node]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) if len(result) == N: return result else: return "IMPOSSIBLE" output = [] for case in test_cases: N, M = case['N'], case['M'] edges = case['edges'] graph = defaultdict(list) in_degree = [0] * (N + 1) for u, v in edges: graph[u].append(v) in_degree[v] += 1 output.append(topological_sort(N, graph, in_degree)) return output # Sample Usage test_cases = [ {'N': 3, 'M': 2, 'edges': [(1, 2), (2, 3)]}, {'N': 4, 'M': 3, 'edges': [(1, 2), (2, 3), (3, 1)]} ] print(find_switch_order(test_cases)) # Expected output: [[1, 2, 3], "IMPOSSIBLE"]

answer:def can_transform(initial_sequence, target_sequence): Returns "Yes" if it is possible to transform initial_sequence into target_sequence using the allowed operations, otherwise returns "No". if sorted(initial_sequence) == sorted(target_sequence): return "Yes" return "No" # Example usage if __name__ == "__main__": import sys input = sys.stdin.read data = input().split() N = int(data[0]) initial_sequence = list(map(int, data[1:N+1])) target_sequence = list(map(int, data[N+1:2*N+1])) print(can_transform(initial_sequence, target_sequence))

answer:from collections import deque, defaultdict def minimum_transfers(L, lines, start, destination): Given the number of subway lines, list of lines with stations, and starting and destination stations, this function calculates the minimum number of transfers needed to travel from start to destination. if start == destination: return 0 # Create a graph where nodes are stations and edges are lines between them station_to_lines = defaultdict(set) line_adjacency = defaultdict(set) for line_id, stations in enumerate(lines): for station in stations: station_to_lines[station].add(line_id) for other_station in stations: if other_station != station: line_adjacency[station].add(other_station) # BFS to find the shortest path in terms of transfers queue = deque([(start, 0)]) visited = set([start]) while queue: current_station, transfers = queue.popleft() if current_station == destination: return transfers - 1 # Subtract one because we start on one of the lines for line in station_to_lines[current_station]: for next_station in lines[line]: if next_station not in visited: visited.add(next_station) queue.append((next_station, transfers + 1)) return -1 # If no path is found

answer:def group_check(s): Returns True if the sequence of braces in the string is valid, otherwise returns False. The braces considered are [], {}, and (). # Stack to keep track of opening braces stack = [] # Dictionary mapping opening braces to their corresponding closing braces matching_brace = {')': '(', '}': '{', ']': '['} for char in s: if char in matching_brace: # If the current char is a closing brace, check if it matches the latest opening brace if stack and stack[-1] == matching_brace[char]: stack.pop() else: return False else: # If the current char is an opening brace, push it to the stack stack.append(char) return not stack