Colors

장난감 회사의 관리자가 생산 라인의 제조 비용을 줄이려고 한다. 장난감은 로봇이 조립 트랙에서 트랙 부품을 추가하고 연결해 모듈로 만들고, 기존 모듈을 더 복잡한 모듈로 병합하는 방식으로 생산한다. 부품은 활성 또는 비활성 상태일 수 있다. 어느 순간이든 각 모듈과 트랙마다 정확히 하나의 활성 부품이 있으며, 그 트랙과 모듈에서 연결하거나 병합할 수 있는 부품은 이 활성 부품뿐이다.

이 회사의 새 예산으로는 세 가지 색으로 이루어지고 인접한 부품끼리 서로 다른 색이어야 하는 부품만 지원할 수 있다. 재고에 있는 장난감 중 이런 색칠 제약 아래에서 생산할 수 있는 것을 판별하라.

회사는 장난감 설계도를 더 정확히 기술하기 위해 다음과 같은 BNF 형식을 사용한다:

1. <toy> ::= <last-track><module>
   • 현재 <toy>는 하나의 주 <module>로 이루어진다. <last-track>은 현재 <toy>를 만드는 데 사용한 마지막 트랙의 번호이며, 트랙은 0부터 <last-track>까지 번호가 매겨진다.
2. <module> ::= ‘(’ <operator-sequence> ‘)’
   • <module>은 연산자만 포함하는 단순 모듈이다. <operator-sequence>가 주는 연산자는 왼쪽에서 오른쪽 순서로 처리된다. 이 <module>은 빈 트랙에서 시작하고, 사용 가능한 각 트랙에 활성 부품을 하나씩 자동으로 추가한다.
3. <merged-module> ::= ‘(’ <module>1<module>2 ‘)’
   • <module>1과 <module>2가 모두 완전히 만들어진 뒤, 두 모듈의 활성 부품을 병합해 복잡한 <merged-module>을 만드는 병합 연산이다.
4. <module> ::= ‘(’ <merged-module><operator-sequence> ‘)’
   • <merged-module>의 부품은 트랙에 남아 있고, 그 활성 부품은 <operator-sequence>가 주는 연산자로 계속 가공된다.
5. <operator-sequence> ::= λ | <operator><operator-sequence>
6. <operator> ::= <node-operator> | <edge-operator>
7. <node-operator> ::= <track-number>
   • <node-operator>는 현재 모듈의 지정된 <track-number>에 활성 부품을 추가하고, 그 트랙에서 이전에 활성이던 부품은 비활성이 된다.
8. <edge-operator> ::= <track-number-pair>
   • <edge-operator>는 두 트랙 번호의 활성 부품을 연결한다.

다음 예는 몇 가지 단순한 장난감 설계도를 보여 준다. 그림에서 트랙은 가로 점선, 부품은 원, 연결은 실선으로 나타내며, 시간 축은 왼쪽에서 오른쪽으로 흐른다.

예 1의 그림 4는 다음 설계도로 만들 수 있는 3색칠 가능한 장난감을 나타낸다:

2 ( 20 10 21 2 20 )

그림 4: 3색칠 가능한 장난감

트랙은 0, 1, 2번 세 개다. 이 장난감은 부품 a, b, c, d를 포함하는 단일 모듈로 이루어지고, c–a, b–a, c–b, d–a 선으로 연결된다. 이 장난감을 만들기 위해 로봇은 다음 연산을 순서대로 실행한다:

1. 트랙 0에 a, 트랙 1에 b, 트랙 2에 c를 추가한다. 이 단계에서 a, b, c가 활성 부품이다.
2. c–a, b–a, c–b 연결을 만든다.
3. 트랙 2에 d를 추가하면 d가 활성이 되고 c는 비활성이 된다.
4. d–a 연결을 만든다. 이 단계에서 a, b, d가 활성 부품이다.

같은 장난감은 다음 두 가지처럼 다른 여러 설계도로도 만들 수 있다:

2 ( 10 20 21 2 20 )
2 ( ( ( 20 10 ) ( 21 ) ) 2 20 )

예 2의 그림 5와 그림 6은 병합이 포함된 연산 순서를 보여 준다. 다음 설계도로 만들 수 있는 또 다른 3색칠 가능한(실은 2색칠도 가능한) 장난감이다:

1 ( ( ( 10 1 10 0 ) ( 10 1 10 0 ) ) 10 1 10 )

그림 5: 병합할 모듈

그림 6: 병합 결과 장난감

1. 먼저 모듈 1을 만든다:

   1. 트랙 0에 a, 트랙 1에 b를 추가한다.
   2. b–a를 연결한다.
   3. 트랙 1에 c를 추가한다.
   4. c–a를 연결한다.
   5. 트랙 0에 d를 추가한다. 이제 c와 d가 모듈 1의 활성 부품이다.

2. 다음으로 비슷한 연산으로 모듈 2를 만든다. 이제 g와 h가 모듈 2의 활성 부품이다.

3. 그다음 모듈 1과 모듈 2를 병합한다. 각 트랙의 활성 부품이 동일시된다. 즉 c = g, d = h이다. 그림 5의 스냅숏은 이 순간을 나타내며, 중괄호는 부품의 동일시를 보여 준다. 이제 (c + g)와 (d + h)가 병합된 모듈 1 + 2의 활성 부품이다.

4. 이어서 방금 병합된 부품을 연결한다. 즉 (c + g)–(d + h)이다.

5. 마지막으로 트랙 1에 i를 추가하고 (d+h)와 연결한다. 최종 결과는 그림 6에 나오고, 병합 후에 만들어진 연결은 이중선으로 표시된다. 끝에서 i와 (d+h)가 주 모듈의 활성 부품이다.

입력은 한 줄에 하나씩, 각각 길이가 250자 이하인 장난감 설계도의 나열이다. 각 장난감 설계도는 공백 하나로 구분된 토큰의 나열이며, 앞서 설명한 BNF 규칙을 따른다.

첫 토큰은 양의 정수 t이고 0 ≤ t ≤ 6이며, 로봇의 팔이 잡을 수 있는 최대 트랙 번호를 나타낸다(즉 로봇에게는 t + 1개의 현재 부품이 있다).

나머지 토큰의 의미는 다음 표와 같다.

입력은 t = 0인 장난감 설명으로 끝나며, 이는 처리하지 않는다.

출력은 “Toy #: ?” 형식의 한 줄이다. #는 1부터 시작하는 장난감 순번이고, ?는 그 장난감을 최대 3가지 색으로 제대로 만들 수 있는지에 따라 Yes 또는 No이다.