Keyboard

Time limit1.5sMemory limit512 MB

Summary

Assign each of N letters to one of two sides so that every given word alternates sides, then minimize the imbalance between the side sizes.

Level: Medium7 of 10
Topics: Graph, BFS, Union-find, Greedy
Solved: No attempts yet

Problem

Juku is an alien. But of course, aliens also need to write texts on their computers. To make this task efficient, Juku is planning to build his own ergonomic keyboard. This includes inventing the layout in which all of the $N$ different letters of his alien alphabet are arranged.

He has listed his $M$ most common words; each of these words should be comfortable to type on the keyboard. A word is comfortable to write on a keyboard if its letters alternate between the right and the left part of the keyboard. On the other hand, it is important that the keyboard is balanced: that is, the absolute difference between the number of keys on the right side and the number of keys on the left side of the keyboard is as small as possible.

Your task is to decide whether such a keyboard can be constructed. If it is possible, calculate the smallest possible absolute difference between the number of keys on the two sides of the keyboard.

Input

The first line of input contains the numbers $N$ and $M$ described above. Then, $M$ lines follow. The first number in the $i$ th of these lines is $K_i$ , the number of characters in Juku's $i$ th most common word. The same line contains $K_i$ further integers between 1 and $N$ (inclusive), each of them denoting a character of the alphabet. In the order in which they appear in the line, they form Juku's $i$ th most common word.

Output

Your program should output a single line. If it is impossible to build a keyboard on which all given words are comfortable to write, print the string impossible. Otherwise, the output should consist of the minimum absolute difference of the number of keys on the left side of the keyboard and the number of keys on the right side, while all $M$ given words are comfortable to write.

Constraints

$1 \le N \le 1\,000\,000$
$M \ge 1$
$K_i \ge 2$
$K_1 + \cdots + K_M \le 1\,000\,000$

Hint

In the first sample, the alien's alphabet consists of the same 26 characters as the English alphabet. When encoding a as 1, b as 2, and so on, the three words in the first input are second, virtual, and boi. The keyboard can be built as follows: the characters e, d, l, o, r, u, and v are on the left side, while the characters a, b, c, i, n, s, and t are on the right side, and the other 12 unused characters are distributed evenly.

In the second sample, the same encoding is used for the words hello and world. Because the first word contains the character l twice without any character between the two occurrences, it is impossible to build a valid keyboard that alternates sides between the two corresponding keystrokes.

In the third sample, one optimal possibility is to put the keys 1, 3, 5, and 6 on the left side, and the keys 2 and 4 on the right side.

Examples3

Example 1

Input

26 3
6 19 5 3 15 14 4
7 22 9 18 20 21 1 12
3 2 15 9

Expected output

Example 2

Input

26 2
5 8 5 12 12 15
5 23 15 18 12 4

Expected output

impossible

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