어셈블러 회로

Bytetel 사는 자사 컴퓨터가 실행하는 어셈블러 프로그램을 어셈블러 회로라는 하드웨어 장치로 바꾸려고 한다.

어셈블러 프로그램은 대입문의 나열이다. 각 대입문은 다음 네 가지 요소로 정해진다.

• 현재 값을 읽어 오는 두 개의 레지스터,
• 그 두 값에 적용하는 하나의 기본 연산,
• 결과를 저장하는 하나의 레지스터.

레지스터는 최대 26개이며 알파벳 소문자 a부터 z까지로 나타낸다. 기본 연산은 최대 4가지이며 알파벳 대문자 A, B, C, D로 나타낸다. 모든 연산은 두 개의 입력값을 순서대로 받아 하나의 출력값을 만든다.

어셈블러 회로는 다음으로 이루어진다.

• 입력: 레지스터마다 하나씩 있으며 해당 레지스터의 초깃값을 전달한다.
• 출력: 레지스터마다 하나씩 있으며 해당 레지스터의 최종값을 전달한다.
• 게이트: 각 게이트는 두 개의 입력과 하나의 출력을 가지며, 입력으로 들어온 두 값에 기본 연산 하나를 적용한다. 게이트의 입력이나 회로의 출력은 회로의 입력 또는 다른 게이트의 출력에 연결할 수 있다. 게이트의 출력이나 회로의 입력은 여러 게이트의 입력과 회로의 출력에 동시에 연결할 수 있다. 이 연결은 사이클을 이루어서는 안 된다.

레지스터의 어떤 초기 상태에 대해서도 프로그램이 만드는 26개 레지스터의 최종값과 회로가 만드는 최종값이 완전히 같으면, 그 회로는 프로그램과 동치이다.

주어진 프로그램과 동치인 어셈블러 회로가 가질 수 있는 게이트의 최소 개수를 구하여라.

첫 번째 줄에 프로그램의 명령어 개수를 나타내는 정수 $n$ ($1 \le n \le 1000$)이 주어진다.

이어지는 $n$개의 줄에는 각 명령어가 네 글자 단어로 주어진다. 첫 번째 글자는 연산 기호(A, B, C, D 중 하나)이다. 두 번째와 세 번째 글자는 입력값이 들어 있는 레지스터의 이름(소문자)이며, 이 순서대로 사용된다. 네 번째 글자는 결과가 저장되는 레지스터의 이름(소문자)이다.

주어진 프로그램과 동치인 어셈블러 회로의 최소 게이트 개수를 정수 하나로 출력한다.