작업 스케줄링

많은 요리에서는 어떤 작업을 다른 작업보다 먼저 끝내야 합니다. 각 작업이 의존하는 다른 작업들의 목록이 주어지면, 의존 관계를 만족하는 작업 순서를 정하는 것은 비교적 간단하며, 이는 위상 정렬(topological sort)이라는 알고리즘으로 해결할 수 있습니다.

하지만 현실은 그렇게 간단하지 않을 때가 있습니다. 예를 들어 피자 도우를 만드는 다음 레시피를 봅시다.

1. 효모를 따뜻한 물에 섞고 5분에서 10분 기다립니다.
2. 나머지 재료를 7분에서 9분 동안 섞습니다.
3. 효모와 나머지 재료를 함께 10분에서 15분 동안 섞습니다.
4. 반죽이 부풀도록 90분에서 120분 기다립니다.
5. 반죽을 눌러 공기를 빼고 10분에서 15분 둡니다.
6. 반죽을 밉니다.

이 경우 작업 1과 2는 첫 1분이 지난 뒤에 시작할 수 있습니다(레시피를 읽고 계획을 세우는 데 항상 첫 1분을 씁니다). 작업 3은 아무리 빨라도 8분에, 작업 4는 시작 후 18분에 시작할 수 있으며, 이런 식으로 이어집니다. 이 레시피는 비교적 단순하지만, 어떤 작업에 의존하는 작업이 많아지면 일정 짜기가 감당하기 어려워집니다. 때로는 레시피를 실제로 실행하는 것이 불가능할 수도 있습니다. 예를 들어 다음과 같은 추상적인 레시피를 생각해 봅시다.

1. 작업 1
2. 작업 1 이후, 그러나 작업 1로부터 2분 이내에 작업 2를 한다.
3. 작업 2로부터 적어도 3분 뒤, 그러나 작업 1로부터 2분 이내에 작업 3을 한다.

이 문제에서는 여러 개의 작업이 주어집니다. 일부 작업은 시작 시각을 기준으로 서로 관계를 가집니다. 모든 제약을 만족하도록 각 작업에 시작 시각을 배정하거나, 그것이 불가능하면 불가능하다고 보고해야 합니다.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 케이스의 첫 줄에는 작업의 수 $n$ ($1 \le n \le 100$)이 주어집니다. 다음 줄에는 제약의 수를 나타내는 음이 아닌 정수 $m$이 주어집니다. 이어지는 $m$개의 줄에는 각각 하나의 제약이 주어지며, 제약은 다음 두 형태 중 하나입니다.

task i starts at least A minutes later than task j
task i starts within A minutes of the starting time of task j

여기서 $i$와 $j$는 서로 다른 두 작업의 번호이고($1 \le i, j \le n$), $A$는 음이 아닌 정수입니다($A \le 150$). 첫 번째 형태는 작업 $i$가 작업 $j$의 시작 시각보다 적어도 $A$분 늦게 시작해야 함을 뜻합니다. 두 번째 형태는 작업 $i$가 작업 $j$보다 일찍 시작하지 않으면서, 작업 $j$의 시작 시각으로부터 $A$분 이내에 시작해야 함을 뜻합니다. 같은 작업 쌍에 대해 여러 제약이 주어질 수 있습니다. '적어도'와 '이내'는 경곗값을 포함합니다(예를 들어 작업 1이 1분에, 작업 2가 4분에 시작하면 작업 2는 작업 1보다 적어도 3분 늦게 시작하며, 작업 1의 시작 시각으로부터 3분 이내에 시작합니다).

입력은 $n = 0$인 줄로 끝납니다.

각 테스트 케이스마다 작업 1부터 작업 $n$까지의 시작 시각을 공백 하나로 구분하여 한 줄에 출력합니다. 각 시작 시각은 그 작업이 시작하는 분을 나타내며, 양의 정수이고 $1000000$보다 작아야 합니다.

유효한 일정이 여러 개일 수 있으므로, 이 문제에서는 가장 이른 일정을 출력합니다. 즉, 모든 제약을 만족하면서 각 작업의 시작 시각을 (동시에) 가능한 한 작게 만드는 일정을 출력하며, 가장 이른 시작 시각은 1분입니다. 유효한 일정들은 좌표별 최솟값을 취해도 다시 유효하므로 이렇게 정의되는 가장 이른 일정은 항상 유일하게 정해집니다. 유효한 일정이 존재하지 않으면 대신 한 줄에 Impossible.을 출력합니다.