게이트

현대 VLSI 칩 산업에서 전기공학자들이 사용하는 소프트웨어 도구는 다양한 최적화를 수행한다. 이 문제에서는 어떤 칩 설계에 대한 한 가지 최적화를 구현한다.

주어지는 것은 NAND 게이트로 이루어진 비순환(acyclic) 회로망이다. (NAND 게이트는 두 입력의 논리곱을 부정한 값을 출력한다. 즉, 두 입력이 모두 1일 때에만 출력이 0이고, 그 밖의 경우에는 1이다.) 이 회로망은 이미 합성이 끝난 부품의 일부이며, 그 구조를 바꿀 수 없다. 회로망의 모든 입력은 하나의 신호 x에 연결되어 있다. 목표는 일부 입력에서 x와의 연결을 끊고 그 입력에 상수 신호 0 또는 1을 대신 연결하되, 전체 설계가 구현하는 함수는 그대로 유지하는 것이다.

회로망의 입력들에 x, 0, 1을 배정하는 방식이 최적(optimal)이라는 것은, 모든 입력을 x에 연결했을 때와 동일한 함수를 회로망이 계산하면서 x에 연결된 입력의 개수가 가능한 한 적은 경우를 말한다.

다음 설계를 살펴보자.

이 설계는 예를 들어 다음과 같이 변수 입력이 하나만 남도록 다시 구성할 수 있다.

(하나의 x와 몇 개의 0, 1로 입력을 연결하여 같은 함수를 구현하는 다른 방법들도 존재한다.)

전체 회로망은 하나의 변수 x에 대한 불 함수를 구현하므로, 그 함수는 상수(x = 0일 때와 x = 1일 때 값이 같음)이거나 상수가 아니다. 따라서 최적 배정에서 x에 연결되는 입력의 개수는 함수가 상수이면 0, 상수가 아니면 1이다.

각 데이터 집합에 대해 다음을 수행하는 프로그램을 작성하라.

• 회로망의 설명을 읽는다,
• x에 반드시 연결된 채로 남아 있어야 하는 입력의 최소 개수를 구한다,
• 그 개수를 출력한다.

입력의 첫째 줄에는 데이터 집합의 개수를 나타내는 양의 정수 d가 하나 주어진다 (1 ≤ d ≤ 20). 그 뒤로 데이터 집합들이 이어진다.

각 데이터 집합은 연속된 두 줄로 이루어진다. 그 첫째 줄에는 공백 하나로 구분된 두 양의 정수 n과 m이 주어진다 (1 ≤ n ≤ 100 000, 1 ≤ m ≤ 200 000). n은 회로망 입력의 개수이고, m은 회로망에 있는 게이트의 개수이다.

그 둘째 줄에는 공백 하나로 구분된, 0이 아닌 정수 2m개가 주어진다. 위치 2j − 1과 2j에 있는 두 수는 게이트 j의 두 입력에 대한 신호 출처를 나타낸다. 양수 s는 게이트 s의 출력을 의미하고, 음수 s는 회로망의 (−s)번째 입력을 의미한다. 게이트와 회로망 입력의 번호는 1부터 매긴다. 각 게이트의 입력은 회로망 입력이거나, 순서상 앞에서 이미 설명된 게이트의 출력에 연결된다. 각 회로망 입력은 적어도 하나의 게이트 입력에 연결된다. 마지막 게이트의 출력은 회로망의 출력에 연결되며, 그 밖의 모든 게이트 출력은 적어도 하나의 게이트 입력에 연결된다.

출력은 정확히 d개의 줄로 이루어지며, 각 데이터 집합에 대해 한 줄씩이다. i번째 줄에는 i번째 데이터 집합에 대한 답, 즉 모든 입력을 x에 연결했을 때와 같은 함수를 회로망이 여전히 계산하도록 하면서 x에 연결된 채로 남아 있어야 하는 입력의 최소 개수를 정수 하나로 출력한다. 이 값은 회로망의 함수가 x에 의존하지 않으면 0, 의존하면 1이다.