#!/usrs/local/bin/perl -w

use strict;

my %paths;
my %labels;

while (<>) {
  next unless /\S/;

  my($label, $duration, @dependencies) = split;

  die "Duplicate label $label on line $..\n" if $labels{$label}++;

  if (@dependencies) {
    foreach my $dependency (@dependencies) {
      die "Label $label depends on itself on line $..\n"
        if $label eq $dependency;

      die "Unknown dependency $dependency on line $..\n"
        if !$labels{$dependency};

      foreach my $path (keys %paths) {
        if ($path =~ / \Q$dependency\E\z/) {
          $paths{"$path $label"} = $paths{$path} + $duration;
        }
      }
    }
  } else {
    $paths{" $label"} = $duration;
  }
}

die "No FINAL label.\n" if !$labels{'FINAL'};

my @critical;
my $max = -1;
foreach my $path (keys %paths) {
  next if $path !~ / FINAL\z/;

  if ($paths{$path} > $max) {
    $max = $paths{$path};
    @critical = $path;
  } elsif ($paths{$path} == $max) {
    push @critical, $path;
  }
}

die "No critical paths.\n" if !@critical;

foreach my $path (@critical) {
  my @path = split ' ', $path;

  print "$_\n" for @path;
  print "\n";
}

