Gift Exchange Cycles

In this problem, you are given a number of friends and a list of allowed gift exchanges between them. Each exchange is represented as a directed edge from one friend to another. The goal is to determine whether it is possible to arrange a gift exchange such that every friend gives and receives exactly one gift, thereby forming one or more cycles that cover all participants.

Mathematically, for each friend ( i ), we require that ( indegree(i) = 1 ) and ( outdegree(i) = 1 ). If this condition is met for all friends, output "Possible"; otherwise, output "Impossible".

inputFormat

The first line of input contains an integer ( T ) representing the number of test cases. For each test case, the first line contains two integers ( N ) and ( M ) where ( N ) is the number of friends and ( M ) is the number of allowed gift exchanges. The next ( M ) lines each contain two integers ( u ) and ( v ) indicating a possible gift exchange from friend ( u ) to friend ( v ).

outputFormat

For each test case, output a single line containing "Possible" if it is possible to arrange the gift exchange so that every friend participates in exactly one cycle, otherwise output "Impossible".## sample

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

Impossible
Possible
Possible