题目描述

题目译自 BalticOI 2021 Day0「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

impossible

因为在第二个数列中出现了 $A_3=A_4=12$，所以不可能有一种划分方案满足条件。

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

2

一种最优的方案是 $S_0=\{1,3,5,6\},S_1=\{2,4\}$。

数据范围与提示

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

详细子任务分值及附加限制如下：

• 子任务 $1$（$40$ 分）：$N\le 5\times 10^3$；
• 子任务 $2$（$30$ 分）：$N\le 10^5$；
• 子任务 $3$（$30$ 分）：无特殊限制。

另外，对于每个子任务，如果您的程序可以正确判断每个测试点是否存在可行方案，您会得到该子任务 $10\%$ 的分数。

具体而言，您会得到该子任务的 $10\%$ 的分数当且仅当对每个测试点：

• 若不存在可行方案，输出 impossible
• 若存在可行方案，输出一行一个任意非负整数

特别地，建议该整数不超过 $N$，否则不保证 SPJ 程序可以正常运行。