키보드

Juku는 외계인이다. 물론 외계인도 컴퓨터로 글을 써야 한다. Juku는 이 작업을 효율적으로 하기 위해 자신만의 인체공학 키보드를 만들려고 한다. 여기에는 외계 문자 $N$종을 배열하는 레이아웃을 고안하는 일도 포함된다.

Juku는 자신이 가장 자주 쓰는 단어 $M$개를 조사했다. 이 단어들은 키보드에서 편하게 입력할 수 있어야 한다. 어떤 단어가 키보드에서 편하게 입력된다는 것은 그 단어의 글자들이 키보드의 오른쪽 부분과 왼쪽 부분을 번갈아 가며 나타난다는 뜻이다. 한편 키보드의 균형도 중요하다. 즉, 오른쪽 키의 개수와 왼쪽 키의 개수의 절댓값 차이가 가능한 한 작아야 한다.

이런 키보드를 만들 수 있는지 판별하시오. 만들 수 있다면, 키보드 양쪽의 키 개수 차이의 절댓값으로 가능한 최솟값을 구하시오.

첫 줄에 위에서 설명한 수 $N$과 $M$이 주어진다. 이어서 $M$개의 줄이 주어진다. 이 중 $i$번째 줄의 첫 번째 수는 Juku가 $i$번째로 자주 쓰는 단어의 글자 수 $K_i$이다. 같은 줄에 1 이상 $N$ 이하의 정수 $K_i$개가 더 주어지며, 각각은 알파벳의 한 글자를 나타낸다. 줄에 나타난 순서대로 Juku가 $i$번째로 자주 쓰는 단어를 이룬다.

한 줄을 출력한다. 주어진 모든 단어를 편하게 입력할 수 있는 키보드를 만들 수 없다면 impossible을 출력한다. 그렇지 않다면, 주어진 $M$개 단어를 모두 편하게 입력할 수 있으면서 키보드 왼쪽 키의 개수와 오른쪽 키의 개수의 절댓값 차이로 가능한 최솟값을 출력한다.

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

첫 번째 예제에서 외계인의 알파벳은 영어 알파벳과 같은 26글자로 이루어져 있다. a를 1, b를 2, 이런 식으로 부호화하면 첫 번째 입력의 세 단어는 second, virtual, boi이다. 키보드는 다음과 같이 만들 수 있다. 글자 e, d, l, o, r, u, v는 왼쪽에 두고, 글자 a, b, c, i, n, s, t는 오른쪽에 두며, 나머지 쓰이지 않은 12글자는 양쪽에 고르게 나눈다.

두 번째 예제에서도 같은 부호화를 쓰면 단어는 hello와 world이다. 첫 번째 단어에는 글자 l이 두 번 나오는데 그 두 번 사이에 아무 글자도 없으므로, 두 번의 키 입력에서 양쪽을 번갈아 가게 하는 키보드는 만들 수 없다.

세 번째 예제에서 최적의 한 가지 방법은 키 1, 3, 5, 6을 왼쪽에, 키 2, 4를 오른쪽에 두는 것이다.