레이팅 미적용Automatic Chemical Manufacturing은 자기 조립(se\(lf-as\)sembly)이라는 공정을 실험하고 있다. 이 공정(p\(ro- ce\)ss)에서는 서로 자연적 친화력이 있는 분자들을 용액에 섞어 두면 저절로(sp\(on- ta\)neously) 더 큰 구조로 조립된다. 하지만 한 가지 문제가 있다. 분자들이 크기가 무한한 구조로 조립되어 기계가 망가지는 경우가 있다. 주어진 분자들의 모음이 크기가 무한한 구조로 조립될 수 있는지 판별하는 프로그램을 작성해야 한다. 두 가지 단순화 가정을 두어야 한다. 1) 문제는 2차원으로 제한되고, 2) 모음의 각 분자는 정사각형으로 표현된다. 정사각형의 네 변은 그 분자가 호환되는 다른 분자와 연결될 수 있는 표면을 나타낸다. 각 테스트 케이스에서 분자 설명들의 집합이 주어진다. 각 분자 유형은 그 변들이 다른 분자의 변과 어떻게 연결될 수 있는지를 나타내는 네 개의 두 글자(t\(wo-ch\)aracter) 연결자 라벨로 설명된다. 연결자 라벨에는 두 종류가 있다.
-
대문자(A, . . . , Z) 뒤에 + 또는(\(by + or\)) −가 붙는다. 두 변은 라벨의 글자가 같고 부호가 다르면 호환된다. 예를 들어 \(A+ is\) 즉 A+는 \(A - bu\)t 즉 A−와 호환되지만 \(A+ or\) \(B\)−와는 호환되지 않는다.
-
0 두 개, 즉 00. 이 라벨이 붙은 변은 어떤 변과도 호환되지 않는다(00 라벨이 붙은 다른 변과도 마찬가지다). 각 유형의 분자는 무제한으로 공급되며 회전하거나 반사할 수 있다고 가정한다. 분자들이 더 큰 구조로 조립될 때, 두 분자의 변은 호환될 때에만 서로 인접할 수 있다. 어떤 변이든 연결자 라벨과 무관하게 아무것에도 연결되지 않는 것(그 변에 인접한 분자가 없는 것)은 허용된다. 그림 A.1은 세 가지 분자 유형과 그것들로 조립될(ass\(em- bl\)ed) 수 있는 유한한 크기의 구조 하나를 보여 준다(이 분자 집합으로 다른 유한 구조들도 가능하다). 그림 A.1: 샘플 입력 1의 그림.
입력은 하나의 테스트 케이스로 이루어져 있다. 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 분자 유형의 수를 나타내는 정수 \(n\) (\(1 \le n \le 40\,000\))이 주어진다. 둘째 줄에는 각각 분자 유형 하나를 설명하는 여덟 글자(eig\(ht-ch\)aracter) 문자열 \(n\)개가 공백 하나로 구분되어 주어진다. 각 문자열은 분자의 네 변을 시계 방향 순서로 나타내는 네 개의 두 글자(t\(wo-ch\)aracter) 연결자 라벨로 이루어진다.
분자 유형 집합이 크기가 무한한 구조를 만들 수 있으면 unbounded를 출력한다. 그렇지 않으면 bounded를 출력한다.
3
A+00A+A+ 00B+D+A- B-C+00C+
bounded
1
K+K-Q+Q-
unbounded