U258567 小逸“抛砖”

古代有词“抛砖引玉”，意为粗略之言引出高人高明之言。 小逸便是如此一位“抛砖”贤王，作为一大瓜皮，于陕某课堂常常“抛砖”，此砖非普通之砖，它将陕某之言引出，正"合"“抛砖引玉”之意。

陕某和小逸有 $t$ 节课，第 $i$ 节课有 $p_i$ 个模块。 对于每一节课的第 $j$ 个模块（$j ≤p_i$）有 $r_{i,j}$ 个关键词，第 $k$ 个关键词为 $s_{i,j,k}$，对应的如果“抛砖”一个关键词 ，则会关键词对应此模块的“玉”，即小逸说出关键词 $x$，则陕某便会引出 $x$ 所在的模块。 当然，小逸太喜欢超纲了，所以如果他所说话中未出现此节课的任意关键词，陕某便会“提醒”他超纲！ 小逸又非常喜欢“抛砖引砖”，所以如果他所说的话有极大可能性不符合课堂模块的正确顺序，你需要帮大家解除疑惑，算出最少让小逸闭嘴多少次即可让他不再打乱课堂顺序，从而实现不再“抛砖引砖”（闭嘴一次即为让小逸所说的话中减少一个关键词，超纲的关键词必须“闭嘴”，使得小逸的话中关键词所在专题组成的数列为不下降序列）。 现在，你需要分析小逸在课堂中的“抛砖”情况。 （现在情况紧急，所以没时间申请内存了，你只有 $150ms$，$5$ MB 的时间和内存！）

第 $1$ 行，一个整数 $t$ 表示有 $t$ 节课。 对于第 $i$ 节课： 第 $1$ 行，一个数 $p_i$ 表示有 $p_i$ 个模块。 第 $2\sim p_i+1$ 行，第 $j$ 行第一个为正整数 $r_{i,j}$ 表示第 $i$ 节课第 $j$ 个模块有关键词个数。后面接 $r_{i,j}$ 个字符串（保证只有小写字母、大写字母、数字，无空格，长度不超过 $100$），第 $k$ 个字符串 $s_{i,j,k}$ 表示第 $i$ 节课第 $j$ 个模块的第 $k$ 个关键词。（保证本节课内所有关键词均不相同） 第 $p_i+2$ 行，一个字符串，含有多个关键词，每个关键词之后有一个空格。（至多 $3000$ 个关键词，关键词可能重复，且算作两次）

对于第 $i$ 节课： 第 $1$ 行，输出“No.$i$: ”，$i$ 表示第 $i$ 节课。 第 $2$ 行，$p_i$ 个整数，第 $j$ 个整数表示第 $i$ 节课第 $j$ 个模块被陕某提起的次数。 第 $3$ 行，一个整数表示这节课中陕某“提醒”超纲的次数 。 第 $4$ 行，一个整数表示让小逸满足要求至少需要“闭嘴”。（此操作不改变小逸的语言，只计算，即为不影响以上三行的计算）

### 样例#1 解释 只有一堂课，第 $1$ 个模块（手拉手模型）有 hand,hands,with,pull,geo 五个关键词；第 $2$ 个模块（手拉脚模型）有 handswith,legs,pull2 三个关键词；第 $3$ 个模块（脚拉脚模型）有 twoleg,pull3 两个关键词。 小逸所说的话中，有 $9$ 个关键词，它们所在模块分别是 $1,2,3,2,3,\texttt{No},1,1,1$ ，其中 $now$ 超纲，所以小逸所“抛砖”分别是模块 $1$ 有 $4$ 次；模块 $2$ 有 $2$ 次；模块 $3$ 有 $2$ 次。对应的陕某所提的模块也如上，一次超纲。 可以计算至少需要闭嘴 $5$ 次。首先，去除 $now$，$1$ 次；再分析，有多种情况： $1.$ 去除第 $2,3,7,8,9$，$5$ 次； $2.$ 去除第 $3,7,8,9$，$4$ 次； $3.$ 去除第 $2,3,4,5$，$4$ 次…… 可见，采取 $2,3$ 情况可以达到最小值 $5$ 次。 ### 数据范围 由于小逸的精力有限，所以保证一下数据范围： $1≤t≤10$ $1≤p_i≤500$ $1≤r_{i,j}≤50$ ### 关于本题的修改 --- #### 2022.11.1 #### 本题已经~~加强~~修改，由小恒提供意见 --- #### 2022.11.4 #### 补充 由于洛谷题目的上传数据解压后必须小于 $50M$ ，可原数据大小超限（随便一个数据都有 $90M$），所以本题为简易版，数据进行缩小，同时时间和内存也缩小了，下面列出原本数据范围： > $1≤t≤100$ $1≤p_i≤5000$ $1≤r_{i,j}≤500$ 题目中每一个输入最后一行小逸所说的话至多含有 $5000$ 个关键词。 > 本题原本限制：时间 $2s$ ，内存 $1$GB --- ### 题解：[U259567 题解](https://www.luogu.com.cn/blog/ZedAnswer/u259567-ti-xie) ### 本题为[yzc20100218](https://www.luogu.com.cn/user/510713)原创，未经允许，禁止改编、套用