the answer is "which village is yours", i think someone said it last page.
the logic is that the cannibal will point to the soldier's village which is safe because he always lies, and the soldier will also point to the safe village because it is the truth.
here is a good one from a good book, don't post if you had to google for the answer
This thing all things devours:
Birds, beasts, trees, flowers;
Gnaws iron, bites steel;
Grinds hard stones to meal;
Slays king, ruins town,
And beats high mountain down.