Party

Time limit1sMemory limit256 MB

Summary

Find the smallest number of parties so each student pairs with a willing volunteer and no volunteer takes two students at one party.

Level: Medium7 of 10
Topics: Graph, Binary search
Solved: No attempts yet

Problem

The department is holding a party. $m$ students have to attend with a partner, and $f$ volunteers are available to be partners.

Each volunteer states in advance which students they are willing to partner. A volunteer never partners a student outside that list.

At one party a volunteer partners at most one student, so a single party may leave some students without a partner. The same volunteers can be invited to several parties instead. A student only has to attend one of those parties with a partner.

Parties are expensive, so fewer is better. Find the smallest number of parties that lets every student attend one of them with a partner.

Input

The first line contains the number of test cases $n$ . ( $1 \le n \le 200$ )

The first line of each test case contains two integers $m$ and $f$ separated by a single space. $m$ is the number of students who need a partner and $f$ is the number of volunteers. ( $1 \le m \le 100$ , $1 \le f \le 50$ )

The next $f$ lines describe the volunteers, line $i$ describing volunteer $i$ . Each line starts with a positive integer giving how many students that volunteer is willing to partner, followed by the numbers of those students separated by spaces. Students are numbered from $0$ to $m-1$ , and the numbers on one line are distinct.

Output

Print one line for each test case. If no number of parties lets every student attend with a partner, print impossible. Otherwise print a single integer, the smallest number of parties needed.

Examples3

Example 1

Input

3
3 3
1 0
1 0
2 1 2
5 3
5 4 3 2 1 0
1 0
2 0 1
3 2
1 0
2 0 1

Expected output

2
3
impossible

Example 2
Input
```
1
1 1
1 0
```
Expected output
```
1
```
Example 3
Input
```
1
6 1
6 0 1 2 3 4 5
```
Expected output
```
6
```