Course Completion Problem

You are given a set of n courses labeled from 1 to n and m prerequisite relations. Each relation is given as a pair of integers a and b indicating that course a must be completed before course b (i.e. $a \to b$). Your task is to determine whether it is possible to complete all the courses.

This problem can be modeled using a directed graph and solved using topological sorting. A valid topological ordering exists if and only if the graph has no cycles. In other words, if a cycle exists the answer is "Impossible"; otherwise, it is "Possible".

Input: The first line contains two integers n and m, where n is the number of courses and m is the number of prerequisite pairs. This is followed by m lines, each line containing two integers a and b representing a prerequisite relation (course a must be completed before course b).

Output: Output a single line: "Possible" if you can complete all courses, or "Impossible" if not.

Note: Courses are numbered from 1 to n.

inputFormat

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

• The first line contains two integers n and m separated by a space.
• The next m lines each contain two integers a and b, indicating that course a is a prerequisite for course b.

outputFormat

The output should be written to stdout and is a single line containing either "Possible" or "Impossible".

5 4
1 2
2 3
3 4
4 5

Possible