Завдання#1804
У більшості рецептів деякі завдання потрібно виконувати раніше за інші. Якщо для кожного завдання у нас є список інших завдань, від яких воно залежить, ми можемо легко створити розклад, який задовольнить усі залежності і дозволить приготувати ідеальну страву. Багато хто знає, що таку задачу можна розв'язати топологічним сортуванням.
Але життя не завжди просте. Наприклад, розгляньмо рецепт приготування тіста для піци:
Змішайте дріжджі з теплою водою, зачекайте 5–10 хвилин.
Змішайте решту інгредієнтів протягом 7–9 хвилин.
Змішайте дріжджі та решту інгредієнтів разом протягом 10–15 хвилин.
Зачекайте 90–120 хвилин, щоб тісто піднялося.
Зімніть тісто і дайте йому відпочити 10–15 хвилин.
Розкачайте тісто.
Наприклад, завдання 1 і 2 можна виконувати після першої хвилини (ми завжди першу хвилину витрачаємо на читання рецепта та планування). Завдання 3 можна розпочинати не раніше ніж через 8 хвилин, а завдання 4 — не раніше, ніж через 18 хвилин після початку, і так далі. Такий розклад простий. Однак якщо деякі завдання мають багато залежностей, складання розкладу може стати складним. Іноді може бути неможливо дотриматися рецепта. Наприклад, розгляньмо такий абстрактний рецепт:
завдання 1
після завдання 1, але не пізніше ніж через 2 хвилини після його початку, виконайте завдання 2
щонайменше через 3 хвилини після початку завдання 2, але не пізніше ніж через 2 хвилини після початку завдання 1, виконайте завдання 3
Вам задано набір завдань. Завдання залежать одне від одного через час початку виконання. Необхідно призначити момент початку для кожного завдання так, щоб усі задані обмеження виконувалися, або повідомити, що це неможливо.
Вхід складається з кількох тестів. У першому рядку кожного тесту знаходиться кількість завдань (1 \le n \le 100). У наступному рядку розташоване невід'ємне ціле число — кількість обмежень. Кожен з наступних рядків описує одне обмеження, яке може бути одного з двох типів:
завдання починається не раніше ніж через хвилин після початку завдання завдання починається не пізніше ніж через хвилин після початку завдання
Тут та — номери двох різних завдань (1 \le i, j \le n), а — невід'ємне ціле число (A \le 150). Перше обмеження означає, що завдання може розпочатися не раніше, ніж через хвилин після початку завдання . Друге обмеження означає, що завдання повинно початися не раніше завдання та не пізніше, ніж через хвилин після його початку. Можливо кілька обмежень для однієї і тієї ж пари завдань. Зверніть увагу, що як інтервали «не раніше», так і «не пізніше» включні (тобто якщо завдання починається на хвилині , а завдання — на хвилині , то завдання починається не раніше ніж через хвилини після завдання , і не пізніше ніж через хвилини від початку завдання ).
Вхід закінчується рядком з n = 0.
Для кожного тесту виведіть в одному рядку моменти початку виконання завдань з по , розділені пробілами. Кожне ціле число повинно вказувати хвилину початку відповідного завдання. Час початку кожного завдання має бути додатним і меншим за . Можливо кілька коректних розкладів; ви можете вивести будь-який з них. Якщо виконати всі обмеження неможливо, виведіть на окремому рядку Impossible.
Приклад 1