Məsələ#1804
Əksər reseptlərdə müəyyən işlərin digərlərindən əvvəl görülməsi lazımdır. Hər bir iş üçün asılı olduğu digər işlərin siyahısı verilsə, bütün asılılıqları təmin edən və mükəmməl yemək hazırlayan bir cədvəl asanlıqla qurula bilər. Bir çox insan bilir ki, belə bir problem topoloji sıralama ilə həll oluna bilər.
Lakin həyat həmişə sadə olmur. Məsələn, pizza xəmirinin hazırlanması üçün resepti nəzərdən keçirin:
Mayanı ilıq su ilə qarışdırın, 5 ilə 10 dəqiqə arası gözləyin.
Qalan inqrediyentləri 7 ilə 9 dəqiqə arası qarışdırın.
Maya ilə qalan inqrediyentləri bir yerdə 10 ilə 15 dəqiqə arası qarışdırın.
Xəmirin qalxması üçün 90 ilə 120 dəqiqə arası gözləyin.
Xəmiri yumruqlayın və 10 ilə 15 dəqiqə arası dincəlməyə qoyun.
Xəmiri yayın.
Məsələn, 1-ci və 2-ci tapşırıqları birinci dəqiqə bitdikdən sonra cədvəlləşdirmək olar (həmişə ilk dəqiqəni resepti oxuyub planlaşdırmağa sərf edirik). 3-cü tapşırığa ən tez 8 dəqiqədə başlamaq olar, 4-cü tapşırıq isə başlanğıcdan ən tez 18 dəqiqə sonra başlana bilər və s. Bu cədvəl sadədir. Amma bəzi tapşırıqların bir çox asılılığı varsa, cədvəlləşdirmək çətinləşir. Bəzən reseptə riayət etmək mümkün olmur. Məsələn, bu abstrakt resepti nəzərdən keçirin:
tapşırıq 1
tapşırıq 1-dən sonra, lakin başlanğıcından 2 dəqiqə ərzində, tapşırıq 2-ni edin
tapşırıq 2-nin başlanğıcından ən azı 3 dəqiqə sonra, lakin tapşırıq 1-in başlanğıcından 2 dəqiqə ərzində tapşırıq 3-ü edin
Sizə bir sıra tapşırıqlar verilib. Tapşırıqlar bir-birindən başlama vaxtları ilə asılıdır. Hər bir tapşırığı başlamaq üçün vaxt təyin etməli və bütün verilmiş məhdudiyyətləri ödəməlisiniz və ya bunun mümkün olmadığını bildirməlisiniz.
Giriş bir neçə testdən ibarətdir. Hər testin birinci sətirində tapşırıqların sayı (1 \le n \le 100) verilib. Növbəti sətirdə qeyri-mənfi tam ədədi — məhdudiyyətlərin sayı verilir. Növbəti sətirin hər birində bir məhdudiyyət təsvir olunur və iki tip ola bilər:
tapşırıq tapşırıq -nin başlanğıcından ən azı dəqiqə sonra başlayır tapşırıq tapşırıq -nin başlanğıcından ən çox dəqiqə sonra başlamalıdır
Burada və iki müxtəlif tapşırığın nömrəsidir (1 \le i, j \le n), isə qeyri-mənfi tam ədəddir (A \le 150). Birinci məhdudiyyət, tapşırıq -nin tapşırıq -dən ən azı dəqiqə sonra başlaya biləcəyini bildirir. İkinci məhdudiyyət isə tapşırıq -nin tapşırıq -dən tez başlamamasını və tapşırıq -nin əvvəlindən dəqiqə ərzində başlamasını tələb edir. Eyni tapşırıq cütlüyü üçün bir neçə məhdudiyyət ola bilər. Həm “ən azı” intervalı, həm də “ən çox” intervalı daxildir (yəni əgər tapşırıq 1-ci dəqiqədə başlayırsa və tapşırıq 4-cü dəqiqədə başlayırsa, tapşırıq , tapşırıq -dən ən azı dəqiqə sonra və tapşırıq -in başlanğıcından ən çox dəqiqə sonra başlamış sayılır).
Girişdə n = 0 olduqda bitir.
Hər bir test üçün tapşırıqların (-dən -ə qədər) başlama vaxtlarını ardıcıl bir sətirdə, aralarında boşluq olmaqla çap edin. Hər bir tam ədəd müvafiq tapşırığın başlama dəqiqəsini göstərməlidir. Hər bir tapşırığın başlama vaxtı müsbət və -dən kiçik olmalıdır. Bir neçə düzgün cədvəl ola bilər; istənilən birini çap edə bilərsiniz. Əgər bütün məhdudiyyətləri ödəmək mümkün deyilsə, bir sətirdə **Impossible.** çap edin.
Nümunə 1