Comment by FussyZeus

I believe Hercules solved this one by cutting all the heads off at the same time. So, in theory, you just need one guillotine per head.