Task#1804
In most recipes, certain tasks must be done before others. If for each task we have a list of other tasks it depends on, we can easily create a schedule that satisfies all dependencies and produces a perfect dish. Many people know that such a problem can be solved by topological sort.
But life is not always simple. For example, consider the recipe for making pizza dough:
Mix the yeast with warm water, wait for 5 to 10 minutes.
Mix the remaining ingredients for 7 to 9 minutes.
Mix the yeast and remaining ingredients together for 10 to 15 minutes.
Wait 90 to 120 minutes for the dough to rise.
Punch the dough and let it rest for 10 to 15 minutes.
Roll the dough.
For example, tasks 1 and 2 can be scheduled after the first minute (we always spend the first minute reading the recipe and planning). Task 3 can be started at the earliest at 8 minutes, and task 4 not earlier than 18 minutes after the start, and so on. This schedule is simple. However, if some tasks have many dependencies, scheduling can become difficult. Sometimes, it may be impossible to follow the recipe. For example, consider this abstract recipe:
task 1
after task 1 but within 2 minutes of its start, do task 2
at least 3 minutes after the start of task 2, but within 2 minutes of the start of task 1, do task 3
You are given a set of tasks. The tasks depend on each other via their starting times. You must assign a starting time to each task so that all given constraints are satisfied, or report that it is impossible.
The input consists of several tests. The first line of each test contains the number of tasks , (1 \le n \le 100). The next line contains a non-negative integer , the number of constraints. Each of the next lines describes a constraint, which can be of two types:
task starts at least minutes after the start of task task starts within minutes after the start of task
Here, and are the numbers of two different tasks (1 \le i, j \le n), and is a non-negative integer (A \le 150). The first constraint means that task can start at least minutes after task starts. The second constraint means that task must start no earlier than task , and within minutes after task starts. There may be multiple constraints on the same pair of tasks. Note that both "at least" and "within" intervals are inclusive (that is, if task starts at minute , and task starts at minute , then task starts at least minutes after task , and within minutes of the start of task ).
The input ends when n = 0.
For each test, output the starting times of tasks through on a single line, separated by spaces. Each integer must specify the minute at which the corresponding task starts. The starting time of each task must be positive and less than . There may be several valid schedules; you may output any of them. If it is impossible to satisfy all constraints, output Impossible. on a separate line.
Example 1