Futbol paradoksları#4882
Braziliya milli futbol komandası dünya çempionu olduqdan sonra İtaliya komandası tərəfindən məğlub edildi. Ardınca, İtaliya komandası Bolqarıstan komandasına uduzdu, Bolqarıstan isə sonuncu dəfə Lüksemburqa məğlub oldu. Bəs bu o deməkdirmi ki, Lüksemburq Braziliyadan güclüdür?
Belə paradokslar tez-tez rast gəlinir, çünki oyunun qalibi olmaq transzitivlik xassəsinə malik deyil. Yəni yuxarıda təsvir edilən vəziyyətin Lüksemburqun Braziliyanı məğlub edəcəyini sübut etməyə kifayət etmir. Bu konsepsiya Petyanı maraqlandırdı və o, bildiyi bütün oyunların nəticələrini analiz etməyə qərar verdi. O, aşağıdakı xassəyə malik ən uzun oyunlar ardıcıllığını tapmaq istəyir: bu ardıcıllıqda istənilən oyunun (yalnız sonuncu oyun istisna olmaqla) qalibi, növbəti oyunda məğlub olmalıdır. Əsas odur ki, ardıcıllıqda olan hər bir növbəti oyun əvvəlkindən sonra baş verməlidir, yəni xronoloji sıra qorunur. Petyanı ardıcıllığın başlanğıcı və sonunun eyni komanda olub-olmaması maraqlandırmır. O üçün ən əsas məsələ ardıcıllığa daxil olan oyunların sayıdır.
Giriş faylında oyunların xronoloji ardıcıllıqla sıralanmış siyahısı verilmişdir, yəni hər bir oyun əvvəlki oyundan sonra baş verir. Birinci sətrdə — oyunların sayı verilib (0 < n \leq 10000). Sonrakı sətrdə hər biri bir oyunu təsvir edən sətr var. Hər oyunun təsviri yeddi simvoldan ibarətdir: ilk üç simvol qalib komandanın identifikatoru, dördüncü simvol tire, beşinci-dördüncü simvollar isə məğlub olan komandanın identifikatorudur. Hər bir komandanın identifikatoru yalnız böyük latın hərflərindən ibarət tam üç simvoldur. Girişdə müxtəlif komanda identifikatorlarının ümumi sayı -dən çox deyil.
Çıxış faylının birinci sətrində, axtarılan ardıcıllığa daxil olan maksimum oyun sayını çap edin. İkinci sətrdə isə ardıcıllığı — əvvəlcə ardıcıllıqda ən son oyunun qalibi, sonda isə ilk oyunun məğlub olan komandası olmaqla, komandaları çap edin. Əgər bir neçə variant varsa, onlardan istənilən birini çap edə bilərsiniz.
Nümunə 1