Task Scheduling Order

You are given n tasks and m dependencies among them. Each task comes with an associated execution time (though this value is not used in determining the order), and each dependency indicates that one task must be completed before another can start. Your goal is to determine a valid order to complete all tasks.

Formally, you are given two integers \(n\) and \(m\), and then:

• A list of \(n\) pairs \((task, time)\), where each pair represents a task and its execution time.
• A list of \(m\) pairs \((u,v)\) indicating a dependency that task \(u\) must be finished before task \(v\) can be started.

If a valid ordering exists (i.e. the dependency graph has no cycles), output "POSSIBLE" on the first line followed by one valid ordering of all task identifiers on the second line. Otherwise, output "IMPOSSIBLE".

inputFormat

The input is read from standard input and has the following format:

The first line contains two integers (n) and (m), where (n) is the number of tasks and (m) is the number of dependencies.

The next (n) lines each contain two integers, representing the task identifier and its execution time.

The following (m) lines each contain two integers (u) and (v), indicating that task (u) must be completed before task (v) can start.

outputFormat

If it is possible to complete all tasks in some order, print "POSSIBLE" on the first line, followed by a second line that lists a valid ordering of the task identifiers (separated by spaces). If it is not possible, print "IMPOSSIBLE".## sample

6 6
1 2
2 3
3 4
4 5
5 1
6 7
1 2
1 3
3 4
4 5
2 5
6 3

POSSIBLE
1 6 2 3 4 5