H :: Mathematics Test

Time Limit: 1 Second    Memory Limit: 32768 KB

A mathematics teacher wants to test her students one by one, on basic math. The teacher uses N balls in the test, on each a single integer is written. In order to test one student (say the i^th student), the teacher first divides all the N balls into K_i non-empty groups, randomly. Then, she asks the student to tell the number of balls and the maximum number written on the balls, for each group. It is supposed to be K_i pairs of integers, considered as the student’s answer.
As an observer from the bureau of education, you are present in the classroom! Initially all you know is N (the number of balls used in the test) and M (the number of students who are taking the test). Later, during the test for student i (1 <= i <= M) you will hear an integer K_i given by the teacher, along with K_i pairs of integers as the student’s answer. These pair of integers are in the format of (a_j, b_j) each, where a_j and b_j are the number of balls and the maximum number for the j^th group respectively (1 <= j <= K_i).
Since you are in love with logical problems, you are curious to figure out whether it is possible that all of these answer be correct using the same set of balls or not!

Input

You are visiting several classes (which means "there are multiple test-cases" in ACM-ICPC lingo!) For each class, you are given two integers N (1 <= N <= 1000) and M (1 <= M <= 1000) in the first line. In the next M lines, the description of each test comes. Each line starts by K_i, the number of groups, followed by 2 × K_i space-separated numbers a₁ b₁ a₂ b₂ ... a_k b_k where a_j is the number of balls in the j^th group and b_j is the maximum number in that group. You may assume all these numbers are positive integers less than or equal to 1,000,000,000.
The last class is empty (N = 0 and K = 0) and it should not be processed.

Output

For each class, the output should be "Impossible" if you have enough evidences (and you are 100% sure) that the students’ answers cannot be all correct at the same time and at least one of them must be wrong. Otherwise, it must be "Possible", where there is a chance the class did well altogether! Write the output without quotation marks.

Sample Input

3 2
2 1 10 2 4
2 1 6 2 10
10 2
2 5 5 5 10
3 3 3 3 6 4 10
0 0

Sample Output

Impossible
Possible

Submit

Source: Tehran, Asia Region - Regional 2011