Check Project Dependencies

You are given multiple projects. Each project consists of a number of tasks and a set of dependencies between tasks.

A dependency pair (a, b) indicates that task a can only be started after task b has been completed. Your task is to determine for each project whether it is possible to finish all tasks without encountering cyclic dependencies.

In other words, for each project with \(n\) tasks and \(m\) dependency pairs, check if there exists a topological ordering of tasks such that for every dependency \( (a, b) \), task \(a\) appears after task \(b\). If such an ordering exists, output "Possible"; otherwise output "Impossible".

This problem can be solved using an algorithm for topological sorting with a time complexity of \(O(n+m)\).

inputFormat

The first line contains an integer \(T\), representing the number of projects.

For each project, the first line contains two integers \(n\) and \(m\) where \(n\) is the number of tasks and \(m\) is the number of dependency pairs.

Then \(m\) lines follow, each containing two integers \(a\) and \(b\) representing a dependency pair. The dependency is interpreted as task \(a\) can only begin after task \(b\) is completed.

outputFormat

For each project, output a single line: "Possible" if it is feasible to finish all tasks under the given dependencies, or "Impossible" if a cyclic dependency prevents completion.

## sample

2
4 2
1 2
3 1
3 3
1 2
2 3
3 1

Possible
Impossible

</p>