题目描述

题目译自 BalticOI $2021$ Day$0$「Keyboard」，译者 cnyz。

本题官网数据压缩包疑似不完整或损坏，因此仅能评测部分完好数据，测试结果不保证准确。

有一个含 $1\sim N$ 的整数集合 $S$，同时有 $M$ 个数列 $A$，第 $i$ 个数列长度为 $K_i$。

试将集合 $S$ 分为 $S_0,S_1$，记 $L_0$ 为 $S_0$ 所含数的个数，$L_1$ 为 $S_1$ 所含数的个数，要求 $S_0\cap S_1=\varnothing$，$S_0\cup S_1=S$，对于每一个数列 $A$，都有 $\forall 1\le i<K_i,A_i\in S_j,A_{i+1}\in S_{j\oplus1}$，且 $|L_0-L_1|$ 最小。

如果有一种可行的方案，请输出最小的 $|L_0-L_1|$，否则，请输出 impossible。

输入格式

第一行两个整数 $N,M$。

接下来 $M$ 行，每行 $K_i+1$ 个整数，第一个整数为 $K_i$，后面 $K_i$ 个整数描述一个数列 $A$。

输出格式

仅输出一行，如果有一种可行的方案，请输出最小的 $|L_0-L_1|$，否则，请输出 impossible。

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

0

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

impossible

数据规模与约定

对于所有数据 $1\le N\le 10^6$，$M\ge 1$，$K_i\ge 2$，$K_1+K_2+\ldots+K_M\le 10^6$。