정육면체 색칠하기

먼 은하 Xos에 A. C. Magnifizer라는 로봇이 산다. 스스로를 “A. C. M.”이라 불리기를 좋아하는 이 로봇은 아름다운 도형을 색칠할 때 가장 행복하다.

어제 늘은 화가가 찾아와 일거리를 맡겼다. 화가의 다음 설치 작품에 쓸 정육면체 하나를 색칠해야 하는데, 화가에게는 그 정육면체가 어떻게 보여야 하는지에 대한 시야(vision) 만 있다.

면 시야(face vision) 는 한 면을 정면으로 바라볼 때 정육면체가 어떻게 보이는지를 나타낸다. 바라보는 면(주면)의 색과, 그 면과 모서리를 공유하는 네 면의 색을 함께 적는다. 이웃한 네 면의 색은 순서가 정해져 있지 않는데, 면 시야는 정확한 배치가 아니라 전체적인 인상만을 담기 때문이다.

정육면체의 시야 는 여섯 면 모두의 면 시야를 모은 것이며, 이 또한 순서는 정해져 있지 않다.

각 면은 영어 대문자 하나로 표시되는 하나의 색으로 칠해진다. 같은 문자는 같은 색을, 다른 문자는 다른 색을 뜻한다. 두 면은 서로 맞은편(대면)이 아닐 때만 이웃(모서리 공유)이므로, 모든 면은 정확히 네 면과 이웃한다. 여섯 면은 아래 그림처럼 1번부터 6번까지 번호가 매겨지며, 대면 쌍은 (1, 6), (2, 4), (3, 5)이다.

정육면체의 시야가 주어졌을 때, 그 시야를 만드는 정육면체의 색칠 방법을 찾아 Magnifizer를 도와라.

한 줄에 공백으로 구분된 여섯 개의 단어가 주어진다. 각 단어는 하나의 면 시야를 나타내며, 정확히 다섯 개의 영어 대문자로 이루어진다. 첫 문자는 주면의 색이고, 나머지 네 문자는 그 면과 이웃한 네 면의 색이다(순서는 상관없다).

색칠은 1번부터 6번까지의 각 면에 대문자 하나를 부여하는 것이다. 어떤 색칠이 만드는 여섯 면 시야의 다중집합이 주어진 면 시야의 다중집합과 같을 때, 그 색칠은 시야를 만족한다(각 면 시야 안에서 이웃한 네 면의 색은 순서 없는 다중집합으로 비교한다).

시야를 만족하는 색칠이 없으면 Impossible 을 출력한다.

그렇지 않으면, 시야를 만족하는 색칠 중 사전순으로 가장 작은 것을 한 줄에 출력한다. 즉 1, 2, 3, 4, 5, 6번 면의 색을 그 순서대로 적은 여섯 글자이다. 정육면체를 회전해서만 달라지는 색칠도 서로 다른 여섯 글자 문자열을 만들므로 그대로 비교하며, 모든 만족 색칠 중 가장 작은 문자열을 출력한다.