Here's a solution (plus extra credit :) at 151:

sub bacon {
  (%g,%d)=@_;for$k(keys%g){($i,@l,%v)=(0,$k);{!$v{$_}++and$d{$k}+=$i f
+or@l;$i++;(@l=map{grep!$v{$_},@{$g{$_}}}@l)&&redo}}(sort{$d{$a}<=>$d{
+$b}}keys%d)[0]
}
[download]

It runs in O(n^2).

   MeowChow                                   
               s aamecha.s a..a\u$&owag.print