Futbol paradoksları
Dünya Futbol Çempionu olan Braziliya millisi, İtaliya millisinə məğlub oldu, İtaliya isə öz növbəsində Bolqarıstan millisinə uduzdu, və Bolqarıstan da Lüksemburq millisinə məğlub oldu. Bu, Lüksemburqun Braziliyadan güclü olduğunu göstərirmi?
Belə paradokslar tez-tez baş verir və buna təəccüblənmək lazım deyil, çünki oyunda qələbə tranzitiv xüsusiyyətə malik deyil. Yəni, yuxarıda təsvir olunanlar Braziliya və Lüksemburq milliləri qarşılaşdıqda mütləq Lüksemburqun qalib gələcəyini ifadə etmir. Bu, Petyanın marağını çəkdi və o, bildiyi bütün oyunların nəticələrini təhlil etməyə və onlardan aşağıdakı xüsusiyyətə malik ən uzun oyun zəncirini seçməyə qərar verdi: bu zəncirdəki istənilən oyunun qalibi (sonuncu istisna olmaqla) növbəti oyunda məğlub olmalıdır. Qeyd edək ki, oyunların xronoloji ardıcıllığı qorunmalıdır, yəni zəncirdəki növbəti oyun əvvəlkindən sonra oynanmalıdır. Petyanı maraqlandıran əsas məsələ, zəncirin eyni komanda ilə başlayıb-bitməsindən asılı olmayaraq, oyunların sayıdır.
Giriş verilənləri
Giriş faylında xronoloji ardıcıllıqla sıralanmış oyunlar ardıcıllığı var, yəni bu ardıcıllıqda hər növbəti oyun əvvəlkindən sonra oynanmışdır. Giriş faylının ilk sətirində n tam ədədi - oynanmış oyunların sayı (0 < n ≤ 10000) verilir. Növbəti n sətirdə hər bir oyunun təsviri var. Hər bir oyun yeddi simvoldan ibarət bir sətirlə təsvir olunur. İlk üç simvol - qalib komandanın identifikatoru, dördüncü simvol - tire, beşinci ilə yeddinci simvollar - məğlub olan komandanın identifikatorudur. Komandanın identifikatoru həmişə üç hərfdən ibarətdir və yalnız böyük latın hərflərindən ibarətdir. Giriş faylında müxtəlif komanda identifikatorlarının sayı 200-dən çox deyil.
Çıxış verilənləri
Çıxış faylının ilk sətirində axtarılan zəncirdəki maksimum oyun sayını göstərin. İkinci sətirdə zəncirin komandalarını, zəncirin son oyununda qalib gələn komandadan başlayaraq, ilk oyunda məğlub olan komanda ilə bitənə qədər göstərin. Əgər ən uzun zəncirlərdən bir neçə variant varsa, onlardan istənilən birini göstərin.