Description

Juku is an alien. But of course, aliens also need to write texts on their computers. To optimize this task, 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 $𝐾_𝑖$, the number of characters in Juku’s $𝑖$ th most common word. The same line contains $𝐾_𝑖$ further integers between $1$ and $𝑁$ (inclusive), each of them denoting a character of the alphabet. In the order in which they appear in the line, they form Juku’s 𝑖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 $𝑀$ given words are comfortable to write.

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

0

In the 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.

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

impossible

In the 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.

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

2

In the 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.

Constraints

We always have $1 \le 𝑁 \le 10^6$, $𝑀 \ge 1$, $𝐾_𝑖\ge 2$, and $𝐾_1+ \ldots + 𝐾_𝑀≤ 10^6$.

• Subtask $1$ ($40$ points). $𝑁 \le 5\times 10^3$
• Subtask $2$ ($30$ points). $𝑁 \le 10^5$
• Subtask $3$ ($30$ points). No further constraints.

Moreover, the following holds: in each subtask, you receive $10\%$ of the points awarded for the respective subtask if your program correctly determines whether it is possible to build an ergonomic keyboard, i.e., it outputs impossible if this is the correct answer and any non-negative integer otherwise.