from collections import defaultdict
import copy

def parse_input(filename):
    rules = []
    updates = []
    with open(filename) as f:
        lines = f.read().strip().split('\n')
        
    # Find the empty line that separates rules and updates
    separator = lines.index('')
    
    # Parse rules
    for line in lines[:separator]:
        x, y = map(int, line.split('|'))
        rules.append((x, y))
    
    # Parse updates
    for line in lines[separator+1:]:
        update = list(map(int, line.split(',')))
        updates.append(update)
    
    return rules, updates

def build_graph(rules):
    # Build adjacency list representation
    graph = defaultdict(list)
    for x, y in rules:
        graph[x].append(y)
    return graph

def is_valid_order(nums, graph):
    # Check if current order satisfies all rules
    num_set = set(nums)
    for i, num in enumerate(nums):
        for next_num in graph[num]:
            if next_num in num_set:
                # If there's a rule num->next_num, check if next_num appears after num
                next_pos = nums.index(next_num)
                if next_pos < i:
                    return False
    return True

def topological_sort(nums, graph):
    # Create a graph only with the numbers in the update
    num_set = set(nums)
    local_graph = defaultdict(list)
    in_degree = defaultdict(int)
    
    # Initialize in-degree for all numbers
    for num in nums:
        in_degree[num] = 0
    
    # Build local graph and calculate in-degrees
    for num in nums:
        for next_num in graph[num]:
            if next_num in num_set:
                local_graph[num].append(next_num)
                in_degree[next_num] += 1
    
    # Find all nodes with in-degree 0
    queue = [num for num in nums if in_degree[num] == 0]
    result = []
    
    while queue:
        current = queue.pop(0)
        result.append(current)
        
        for next_num in local_graph[current]:
            in_degree[next_num] -= 1
            if in_degree[next_num] == 0:
                queue.append(next_num)
    
    return result

def get_middle_number(nums):
    return nums[len(nums)//2]

# Read and parse input
rules, updates = parse_input("input.txt")
graph = build_graph(rules)

# Part 1: Sum middle numbers of correctly ordered updates
valid_sum = 0
invalid_updates = []

for update in updates:
    if is_valid_order(update, graph):
        valid_sum += get_middle_number(update)
    else:
        invalid_updates.append(update)

print(str(valid_sum))

# Part 2: Sum middle numbers of corrected invalid updates
invalid_sum = 0

for update in invalid_updates:
    sorted_update = topological_sort(update, graph)
    invalid_sum += get_middle_number(sorted_update)

print(str(invalid_sum))