Şam yeməyi
Şam yeməyi
Artıq bir neçə ildir ki, praktik kombinatorların şimal konfransı (NCPC) daha çox iştirakçı cəlb edir. Bu il təşkilat komandası rekord sayda iştirakçı gözləyir. Bu nüfuzlu tədbirin təşkili siyasəti ilə bağlı olaraq konfransın saytında artıq çoxdan bildirilmişdir ki, o Stokholda Qrand Mehmanxanasında keçiriləcək. Mehmanxanada iki böyük yemək zalı var, lakin təəssüf ki, bu zalların hər birinə NCPC iştirakçılarının yalnız üçdə ikisi yerləşə bilər, buna görə də iştirakçıları iki qrupa ayırmaq lazım gələcəkdir.
Bu mədudiyyət konfrans zamanı bütün komandaların iştirakı üçün təşkilatçılardan bir neçə yaradıcılıq təfəkkürü tələb edir: onlar iştirakçıları hər birində bütün qrupun 2/3–dən çox olmayaraq iki qrupa bölə bilərlər. Görüş zamanı qrupa bölmənin elə bir neçə ağıllı qaydası tətbiq edilir ki, şam yeməyi zamanı onların digər iştirakçılara öz maraqları haqqıda danışa bilsinlər. Axır ki, hələlik elə dahi məntiq qaydaları vardır ki, bunlara əsasən təyin etmək olar ki, iki yemək zalından hansında Siz oturacaqsınız, Siz (riyaziyyatçı kimi) bundan yalnız xöşlana bilərsiniz! Bir neçə fikirdən sonra onların ağlına iştirakçıları bölmək üçün belə bir fikir gəldi: iştirakçıları iki qrupa bölmək üçün elə minimal Y ili seçmək lazımdır ki, birinci qrupdakı hər bir cütlük Y ilə qədər ilk dəfə göröşmüş olsunlar və ikinci qrupun hər bir cütlüyü ilk dəfə olaraq Y ilində və ya Y ildən sonra görüşmüş olsunlar. Onlardan hər biri üçün bu qərarı uyğun qayda kimi dəqiq qiymətləndirmə qərarına gəlindi, lakin qanunauyğun sual meydana gəldi, bu mümkündürmü?
Giriş verilənləri
Giriş faylının birinci sətrində iştirakçıların sayı - N tam ədədi (4 ≤ N ≤ 400) və birinci görüşdən tanış olanların c sayı verilir. Növbəti hər bir c sətir a b y formatında verilir, yəni, a və b (1 ≤ a < b ≤ n) iştirakçıları ilk dəfə y (1948 ≤ y < 2008) ilində göröşmüşlər. Siyahıda heç bir cütlük bir dəfəfədən çox görüşməmişlər və siyahıda elə bir cütlük yoxdur ki, ehtimal olunduğu kimi, yalnız indi (cari ildə 2008) görüşürlər.
Çıxış verilənləri
Hər bir test üçün ən kiçik Y ilini elə verin ki. iştirakçıları iki qrupa elə bölmək olsun ki, qrupların heç birində 2n/3–dən artıq adam olmasın, belə ki, birinci qrupdakı hər bir adam Y ilinə qədər ilk dəfə göröşmüşlər, ikinci qrupdakı hər bir adam isə ilk dəfə Y ilində və ya sonra görüşmüşlər. Əgər belə bir har olmazsa, "Impossible" verin.
Nümunə
4 6 1 2 1987 2 3 1987 1 3 1987 2 4 1987 1 4 1987 3 4 1987
Impossible