Tübitak Genç Takım Seçme 2016 Soru 8

[Eray]

$2016$ kentten oluşan bir ülkede $k$ kent ikilisi arasında karşılıklı uçak seferleri her kentten her kente ulaşılacak şekilde nasıl düzenlenirse düzenlensin; herhangi ikisi arasında direkt uçuş bulunmayan birkaç kent seçilip bu kentlerin tüm uçuşlarını kaldırarak birinden diğerine ulaşılamayan iki seçilmemiş kentin bulunması sağlanabiliyorsa, $k$ nın alabileceği en büyük değer nedir?

(Azer Kerimov)