The Moral Dilemma

Hibiki and Dita는 서로 사랑하지만, 오랫동안 갈등을 빚어 온 공동체들에 각각 속해 있다. Hibiki는 이 상황을 매우 걱정하며, Dita와의 관계가 사랑의 행위인지 배신의 행위인지 알아내고 싶다.

Hibiki는 자신의 결정에 영향을 줄 여러 이진 특성을 준비하고, 그 위에 세 층으로 이루어진 논리 회로를 만들었다. 각 층은 하나 이상의 논리 게이트. 각 게이트는 "or", "and", "nor"(논리합의 부정), "nand"(논리곱의 부정) 중 하나이다. 첫 번째 층의 각 게이트는 정확히 두 특성에 연결되어 있다. 두 번째 층의 각 게이트는 첫 번째 층의 정확히 두 게이트에 연결되어 있다. 세 번째 층에는 "or" 게이트가 하나만 있으며, 이 게이트는 두 번째 층의 모든 게이트에 연결되어 있다(다시 말해, 전체 회로는 두 번째 층의 게이트 중 적어도 하나가 1을 출력할 때, 그리고 그럴 때에만 1을 출력한다).

문제는 Hibiki가 사람이 사랑에 빠지면 논리적으로 사고하는 능력이 급격히 저하된다는 사실을 아주 잘 알고 있다는 것이다. 특히 사랑에 빠진 사람이 머릿속으로 논리 회로를 계산하면 모든 게이트가 원래 계산해야 했던 값과 반대되는 값을 계산한다는 사실이 잘 알려져 있다. 예를 들어, "or" 게이트는 두 입력이 모두 영일 때, 그리고 그럴 때에만 1을 반환하고, "t{nand}" 게이트는 두 입력이 모두 하나일 때, 그리고 그럴 때에만 1을 출력하는 식이다.

특히 마지막 층의 "or" 게이트도 반대 결과를 출력하므로, Hibiki가 사랑에 빠졌다면 전체 회로는 두 번째 층의 모든 게이트가 0을 출력했을 때, 그리고 그럴 때에만 1을 출력한다.

Hibiki는 사랑이 자신의 결정에 영향을 미치게 둘 수 없다. 그는 가능한 모든 입력에 대한 회로의 출력이 Hibiki가 사랑에 빠졌는지 여부에 의존하지 않도록 하기 위해 두 번째 층에서 제거해야 하는 게이트의 최소 개수를 알고 싶다.

첫 번째 줄에는 세 정수 n, m, k (2 ≤ n, m ≤ 50; 1 ≤ k ≤ 50)가 주어진다. 각각 입력 특성의 개수, 첫 번째 층의 게이트 개수, 두 번째 층의 게이트 개수이다.

두 번째 줄에는 첫 번째 층을 설명하는, 공백으로 구분된 m쌍의 문자열이 주어진다. 각 쌍의 첫 번째 문자열은 게이트를 나타내며("and", "or", "nand", "nor" 중 하나), 두 번째 문자열은 그 게이트가 연결된 두 입력 특성을 나타낸다. 이 문자열은 정확히 n개의 문자로 이루어지며, 게이트가 연결된 입력 특성에 해당하는 정확히 두 문자는 'x'이고 나머지 문자는 ".'이다.

세 번째 줄에는 같은 형식으로 두 번째 층을 설명하는, 공백으로 구분된 k쌍의 문자열이 주어진다. 입력 매개변수를 나타내는 문자열의 길이는 m이며 첫 번째 층의 게이트들에 대응한다.

남은 회로의 출력이 Hibiki가 사랑에 빠졌는지 여부에 의존하지 않도록 하기 위해 두 번째 층에서 제거해야 하는 게이트의 개수를 출력한다.

게이트를 몇 개 제거하더라도 회로의 출력이 계속 Hibiki의 감정에 의존한다면 -1을 출력한다.

첫 번째 예제에서 첫 번째 층의 두 게이트는 같은 입력에 연결되어 있지만, 첫째 게이트는 "and"을 계산하고 둘째 게이트는 "nand"을 계산한다. 따라서 입력이 무엇이고 Hibiki가 사랑에 빠졌는지 여부가 어떠하든 두 게이트의 출력은 항상 서로 다르다. 두 번째 층에는 "or" 게이트와 "and" 게이트가 있으며, 둘 다 첫 번째 층의 두 게이트에 연결되어 있다. If Hibiki가 사랑에 빠지지 않았다면, 입력 특성의 값이 무엇이든 "and" 게이트는 0을 출력하고 "or" 게이트는 1을 출력하며, 세 번째 층의 마지막 "or" 게이트는 항상 최종 답으로 1을 출력한다. If Hibiki가 사랑에 빠졌다면, 입력이 무엇이든 두 번째 층의 "and" 게이트는 1을 출력하고 "or" 게이트는 0을 출력하며, 세 번째 층의 마지막 "or" 게이트는 최종 답으로 0을 출력한다. 따라서 두 번째 층의 두 게이트를 모두 유지하면 회로의 출력은 Hibiki가 사랑에 빠졌는지 여부에 의존한다. 두 번째 층의 두 게이트 중 어느 하나라도 제거하면 회로의 출력은 더 이상 Hibiki가 사랑에 빠졌는지 여부에 의존하지 않으므로 답은 1이다.

두 번째 예제에서는 두 번째 층에 어떤 게이트들을 남기더라도 회로의 출력이 Hibiki가 사랑에 빠졌는지 여부에 의존한다.

세 번째 예제에서는 Hibiki가 두 번째 층의 둘째, 셋째, 넷째 게이트를 유지하면 회로는 Hibiki가 사랑에 빠졌는지 여부에 의존하지 않는다. 다른 방법으로는 첫째 게이트와 마지막 게이트를 유지할 수 있다. 전자는 게이트 두 개를 제거해야 하고 후자는 게이트 세 개를 제거해야 하므로 전자가 더 좋으며, 답은 2이다.