Məsələ
Əksər reseptlərdə bəzi addımların digərlərindən əvvəl yerinə yetirilməsi tələb olunur. Hər bir tapşırıq üçün onun asılı olduğu digər tapşırıqların siyahısı varsa, bu tapşırıqları düzgün ardıcıllıqla yerinə yetirərək mükəmməl bir yemək hazırlaya bilərik. Çoxlarımız bilirik ki, belə bir məsələ topoloji sıralama vasitəsilə həll edilə bilər.
Amma həyat həmişə sadə deyil. Məsələn, pizza xəmirinin hazırlanması reseptinə baxaq:
Mayanı ilıq su ilə qarışdırın, 5 ilə 10 dəqiqə gözləyin.
Qalan inqrediyentləri 7 ilə 9 dəqiqə qarışdırın.
Mayanı və qalan inqrediyentləri 10 ilə 15 dəqiqə qarışdırın.
Xəmirin qalxması üçün 90 ilə 120 dəqiqə gözləyin.
Xəmiri yoğurun və 10 ilə 15 dəqiqə dincə qoyun.
Xəmiri yaymaq.
Məsələn, 1 və 2 tapşırıqları birinci dəqiqədən dərhal sonra yerinə yetirilə bilər (biz həmişə resepti oxumaq və işimizi planlaşdırmaq üçün birinci dəqiqəni istifadə edirik). 3 tapşırığı ən tez 8-ci dəqiqədə başlaya bilər, 4 tapşırığı isə yalnız 18-ci dəqiqədə başlaya bilər və s. Bu sadə bir cədvəldir. Amma bəzi tapşırıqlar çox asılılığa malik olarsa, cədvəl tərtib etmək kifayət qədər çətin bir işə çevrilir. Bəzən hətta resepti yerinə yetirmək mümkün olmur. Məsələn, aşağıdakı abstrakt reseptə baxaq:
tapşırıq 1
tapşırıq 1-dən sonra, amma onun başlanmasından 2 dəqiqə ərzində, tapşırıq 2 yerinə yetirin
tapşırıq 2-nin başlanmasından ən azı 3 dəqiqə sonra, amma tapşırıq 1-in başlanmasından 2 dəqiqə ərzində, tapşırıq 3 yerinə yetirin
Sizin bir sıra tapşırıqlarınız var. Tapşırıqlar başlanma vaxtlarına görə bir-birindən asılıdır. Siz hər bir tapşırıq üçün başlanma vaxtını təyin etməlisiniz ki, bütün verilmiş şərtlərə cavab versin, ya da onların yerinə yetirilməsinin mümkün olmadığını bildirin.
Giriş verilənləri
Bir neçə testdən ibarətdir. Hər bir testin ilk sətiri tapşırıqların sayını n, (1 ≤ n ≤ 100) ehtiva edir. Növbəti sətir məhdudiyyətlərin sayını göstərən qeyri-mənfi tam ədəd m ehtiva edir. Növbəti m sətir hər bir məhdudiyyəti təsvir edir. Onlar iki növdə ola bilər:
tapşırıq i tapşırıq j-nin başlanmasından ən azı A dəqiqə sonra başlayır tapşırıq i tapşırıq j-nin başlanmasından A dəqiqə ərzində başlayır
burada i və j iki fərqli tapşırığın nömrələridir (1 ≤ i, j ≤ n), və A qeyri-mənfi tam ədəddir (A ≤ 150). Birinci məhdudiyyət tapşırıq i-nin tapşırıq j-nin başlanmasından ən azı A dəqiqə sonra başlaya biləcəyini bildirir. İkinci məhdudiyyət tapşırıq i-nin tapşırıq j-nin başlanmasından əvvəl və A dəqiqə ərzində başlamalı olduğunu bildirir. Eyni tapşırıq cütlüyünə bir neçə məhdudiyyət tətbiq oluna bilər. Qeyd edək ki, "ən azı" və "ərzində" şərtlərində vaxt intervalının sərhədləri daxil edilir (yəni əgər tapşırıq 1 1-ci dəqiqədə başlayırsa və tapşırıq 2 4-cü dəqiqədə başlayırsa, onda tapşırıq 2 tapşırıq 1-dən ən azı 3 dəqiqə sonra başlayır və tapşırıq 1-in başlanmasından 3 dəqiqə ərzində başlayır).
Giriş məlumatları n = 0 olduqda bitir.
Çıxış verilənləri
Hər bir test üçün ayrı sətirdə 1-dən n-ə qədər tapşırıqların başlanma vaxtlarını bir boşluqla ayıraraq çıxarın. Hər bir rəqəm müvafiq tapşırığın başlayacağı dəqiqəni göstərməlidir. Hər bir tapşırığın başlanma vaxtı müsbət və 1000000-dən kiçik olmalıdır. Axtarılan uyğun cədvəllər bir neçə ola bilər, siz onlardan hər hansı birini çıxarmalısınız. Əgər bütün məhdudiyyətlərə cavab verən cədvəl mövcud deyilsə, ayrı sətirdə Impossible. çıxarın.