import sys import collections def main(): lines = sys.stdin.read().splitlines() order_rules = set() updates = [] i = 0 n = len(lines) while i < n and lines[i].strip(): line = lines[i].strip() if '|' in line: x, y = line.split('|') x = int(x) y = int(y) order_rules.add((x, y)) i += 1 while i < n and not lines[i].strip(): i += 1 while i < n: line = lines[i].strip() if line: update = [int(x) for x in line.split(',')] updates.append(update) i += 1 middle_pages_correct = [] middle_pages_incorrect = [] for update in updates: position = {page: idx for idx, page in enumerate(update)} valid = True for x, y in order_rules: if x in position and y in position: if position[x] >= position[y]: valid = False break if valid: mid_index = len(update) // 2 middle_page = update[mid_index] middle_pages_correct.append(middle_page) else: pages_in_update = set(update) graph = collections.defaultdict(list) indegree = collections.defaultdict(int) for x in pages_in_update: indegree[x] = 0 for x, y in order_rules: if x in pages_in_update and y in pages_in_update: graph[x].append(y) indegree[y] += 1 queue = collections.deque([node for node in pages_in_update if indegree[node] == 0]) sorted_pages = [] while queue: node = queue.popleft() sorted_pages.append(node) for neighbor in graph[node]: indegree[neighbor] -= 1 if indegree[neighbor] == 0: queue.append(neighbor) if len(sorted_pages) != len(pages_in_update): print("Cycle detected in ordering rules. Cannot perform topological sort.") sys.exit(1) mid_index = len(sorted_pages) // 2 middle_page = sorted_pages[mid_index] middle_pages_incorrect.append(middle_page) total_incorrect = sum(middle_pages_incorrect) print(total_incorrect) if __name__ == "__main__": main()