Nový kápo

Don Giovanni, kápo největší sicilské mafie, už má svá nejlepší léta za sebou a šušká se, že se chystá odejít do ústraní. Všechny teď samozřejmě zajímá, kdo bude novým kápem, aby si u něj včas stihli zajistit přízeň. Pravidla pro to, aby člověk mohl být kápem, jsou vlastně celkem jednoduchá:

• všichni mafiáni se ho bojí,
• on sám se nebojí nikoho.

Otázka nástupníka by zajímala i organizaci pro boj s organizovaným zločinem. Vědí totiž, že pokud by žádný vhodný kandidát neexistoval, mafiáni by se mezi sebou rozhádali a bylo by snadné poštvat je proti sobě.

Proto do mafie vyslali svého informátora. Ten se vždy může pro libovolné dva mafiány x, y zeptat, zda se mafián x bojí mafiána y. Může se přitom klidně stát, že se ani jeden mafián druhého nebojí, nebo že se bojí jeden druhého navzájem. Informátor by se samozřejmě chtěl dohromady zeptat co nejméněkrát, protože nechce skončit jako potrava pro ryby.

V této úloze budete vymýšlet interaktivní algoritmus. Ten nedostane žádný vstup, místo toho má ale přístup k orákulu, kterému může pokládat dotazy (v této úloze konkrétně dotazy tvaru "bojí se mafián x mafiána y?"). Vaším úkolem je zjistit, zda existuje vhodný kandidát na kápa, tj. mafián, kterého se všichni bojí, ale on se nebojí nikoho. Primárně nás přitom zajímá asymptotický počet volání orákula, sekundárně asymptotická časová složitost (předpokládejte, že jedno zavolání orákula stojí konstantně času).