CF993F The Moral Dilemma

Hibiki 和 Dita 相互深爱，但他们分别属于长期冲突的两个群体。Hibiki 对当前的局势非常担忧，他想弄清楚自己与 Dita 的关系究竟是真爱，还是一种背叛行为。 Hibiki 准备了若干个二元特征，并基于这些特征构建了一个三层逻辑电路，每一层由一个或多个逻辑门组成。电路中的每个门要么是“or”，要么是“and”，要么是“nor”（或非），要么是“nand”（与非）。第一层的每个门恰好连接两个特征。第二层的每个门恰好连接第一层的两个门。第三层只有一个“or”门，连接所有第二层的门（换句话说，整个电路的输出为 1，当且仅当第二层至少有一个门输出 1）。 问题在于，Hibiki 很清楚，恋爱中的人逻辑思维能力会大幅下降。特别地，众所周知，恋爱中的人在脑海中评估逻辑电路时，每个门的输出都会与本应输出的结果相反。例如，“or”门仅当两个输入都为 0 时输出 1，“nand”门仅当两个输入都为 1 时输出 1，等等。 尤其是，最后一层的“or”门也会输出相反的结果，因此如果 Hibiki 恋爱了，整个电路仅当第二层所有门都输出 0 时才输出 1。 Hibiki 不希望自己的判断被爱情影响。他想知道，最少需要移除第二层多少个门，才能保证无论输入如何，电路的输出都不会依赖于 Hibiki 是否恋爱。

第一行包含三个整数 $n$、$m$、$k$（$2 \le n, m \le 50$；$1 \le k \le 50$），分别表示输入特征的数量、第一层门的数量、第二层门的数量。 第二行包含 $m$ 对字符串，描述第一层。每对中的第一个字符串表示门的类型（"and"、"or"、"nand" 或 "nor"），第二个字符串为长度为 $n$ 的字符串，恰有两个字符为 'x'（表示该门连接的输入特征），其余字符为 '.'。 第三行包含 $k$ 对字符串，描述第二层，格式同上，但输入参数字符串长度为 $m$，对应第一层的门。

输出需要移除的第二层门的最小数量，使得剩余电路的输出不再依赖于 Hibiki 是否恋爱。 如果无论移除多少门，电路的输出依然依赖于 Hibiki 的感情状态，输出 $-1$。

在第一个样例中，第一层的两个门连接相同的输入，但一个计算“and”，另一个计算“nand”，因此无论输入和 Hibiki 是否恋爱，它们的输出总是不同。第二层有“or”和“and”门，都连接到第一层的两个门。如果 Hibiki 没有恋爱，“and”门总输出 0，“or”门总输出 1，第三层的“or”门最终总输出 1。如果 Hibiki 恋爱了，“and”门总输出 1，“or”门总输出 0，第三层“or”门最终总输出 0。因此，如果保留第二层的两个门，电路的输出依赖于 Hibiki 是否恋爱。如果去掉第二层的任意一个门，电路的输出将不再依赖于 Hibiki 是否恋爱，所以答案是 1。 在第二个样例中，无论保留第二层哪些门，电路的输出都依赖于 Hibiki 是否恋爱。 在第三个样例中，如果 Hibiki 保留第二层的第 2、3、4 个门，电路的输出将不依赖于 Hibiki 是否恋爱。或者，他也可以保留第 1 和最后一个门。前者需要移除 2 个门，后者需要移除 3 个门，因此前者更优，答案为 2。 由 ChatGPT 4.1 翻译