use std::io;
use std::io::BufRead;
use std::cmp::Ordering;
use std::collections::BinaryHeap;

#[derive(PartialEq, Eq)]
struct Decreasing<T>(T);

impl<T: PartialOrd> PartialOrd for Decreasing<T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        other.0.partial_cmp(&self.0)
    }
}

impl<T: Ord> Ord for Decreasing<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        other.0.cmp(&self.0)
    }
}

fn simulation(nexts: &[Vec<u8>], nelves: i32, basetime: i32, inctime: i32) -> (String, i32) {
    let mut incoming = [0 as u8; 26];
    for tos in nexts.iter() {
        for &to in tos {
            incoming[to as usize] += 1;
        }
    }

    let mut sources = BinaryHeap::new();
    for i in 0..26 {
        if incoming[i as usize] == 0 {
            sources.push(Decreasing(i as u8));
        }
    }

    #[derive(PartialEq, Eq, PartialOrd, Ord)]
    struct Completed {
        time: i32,
        job: u8,
    };
    let mut evqu = BinaryHeap::new();

    let mut order = String::new();
    let mut elves = nelves;
    let mut current_time = 0;

    loop {
        while elves > 0 && sources.len() > 0 {
            let Decreasing(job) = sources.pop().unwrap();
            evqu.push(Decreasing(Completed {time: current_time + basetime + inctime * (job as i32 + 1), job}));
            elves -= 1;
        }

        match evqu.pop() {
            Some(Decreasing(event)) => {
                current_time = event.time;
                order.push(char::from(event.job + 65));

                for &to in &nexts[event.job as usize] {
                    incoming[to as usize] -= 1;
                    if incoming[to as usize] == 0 {
                        sources.push(Decreasing(to));
                    }
                }

                elves += 1;
            }
            None => break
        };
    }

    (order, current_time)
}

pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
    let mut nexts: Vec<Vec<u8>> = vec![vec![]; 26];
    for l in reader.lines().map(|l| l.unwrap()) {
        let (from, to) = (l.as_bytes()[5] - 65, l.as_bytes()[36] - 65);
        nexts[from as usize].push(to);
    }

    let part1 = simulation(&nexts, 1, 1, 0).0;
    let part2 = simulation(&nexts, 4, 60, 1).1.to_string();

    Ok((part1, part2))
}