eolymp
bolt
Try our new interface for solving problems
Məsələlər

Şam yeməyi

Şam yeməyi

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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 (4N400) 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, ab (1a < bn) iştirakçıları ilk dəfə y (1948y < 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ə

Giriş verilənləri #1
4 6
1 2 1987
2 3 1987
1 3 1987
2 4 1987
1 4 1987
3 4 1987
Çıxış verilənləri #1
Impossible
Mənbə 2008 Nordic Collegiate Programming Contest, October 4, Problem D