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 ith student), the teacher first divides all the N balls into Ki 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 Ki 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 Ki given by the teacher, along with Ki pairs of integers as the student’s answer. These pair of integers are in the format of (aj, bj) each, where aj and bj are the number of balls and the maximum number for the jth group respectively (1 <= j <= Ki).
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 Ki, the number of groups, followed by 2 × Ki space-separated numbers a1 b1 a2 b2 ... ak bk where aj is the number of balls in the jth group and bj 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.

```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