파이썬 프로그래머를 구하라!

살아남은 파이썬 프로그래머 팀은 모두 여섯 팀뿐이며, 이들은 은신처(안전 가옥) 네트워크를 함께 사용한다. 세 팀은 CPython을 쓰며 가옥 a, b, c에서 시작하고, 나머지 세 팀은 Jython을 쓰며 가옥 d, e, f에서 시작한다.

여섯 팀은 은신처를 서로 맞바꾸려 한다. 즉, 모든 CPython 팀은 Jython 팀들이 처음 있던 가옥으로 옮겨 가고, 모든 Jython 팀은 CPython 팀들이 처음 있던 가옥으로 옮겨 가야 한다. 안내자 Guido는 매일 밤 정확히 한 팀만을, 지금 있는 가옥에서 그와 직접 연결된 이웃 가옥으로 이동시키며, 교환이 끝날 때까지 이 과정을 밤마다 반복한다.

규칙:

• 각 가옥에는 한 팀만 있을 수 있으므로, 팀은 현재 비어 있는 가옥으로만 이동할 수 있다.
• 두 진영은 서로를 불신하므로, Guido는 옮기는 팀의 종류를 번갈아 골라야 한다. 어느 밤에 CPython 팀을 옮겼다면 다음 밤에는 Jython 팀을, 그다음에는 다시 CPython 팀을 옮겨야 한다. 단, 첫날 밤에는 두 종류 중 어느 쪽을 옮겨도 된다.
• 같은 종류의 팀끼리는 서로 구별하지 않는다. 가옥 d, e, f가 (순서에 상관없이) CPython 팀들로, 가옥 a, b, c가 Jython 팀들로 채워지는 순간 교환이 완료된다.

은신처는 최대 스무 개이며, 각각 하나의 소문자로 표시된다. 교환을 끝내는 데 필요한 최소 밤 수를 구하라. 불가능하다면 그 사실을 알려라.

입력은 하나 이상의 시나리오로 이루어지며, 각 시나리오는 한 줄에 하나씩 주어지고 파일 끝에서 끝난다. 각 줄은 하나의 은신처 네트워크를 공백으로 구분된 '단어'들로 기술한다. 한 단어에서 첫 글자는 어떤 가옥을 가리키고, 그 뒤에 오는 각 글자는 그 가옥과 직접 연결된(하룻밤 만에 오갈 수 있는) 가옥을 가리킨다. 모든 연결은 양방향이다.

각 시나리오마다 여섯 팀을 맞바꾸는 데 필요한 최소 밤 수를 한 줄에 하나씩 출력한다. 교환을 결코 완료할 수 없다면 대신 No solution. 을 출력한다.

그림 1~3은 난이도가 점점 높아지는 예시 퍼즐을 보여 준다. 직접 손으로 풀어 볼 수도 있다. CPython 팀이 처음 있는 가옥에는 한 종류의 동전을, Jython 팀이 처음 있는 가옥에는 다른 종류의 동전을 올려 두고, 위 규칙을 지키며 연결을 따라 밀어 옮겨 보면 된다.

그림 1: 적당히 어려운 퍼즐

그림 2: 더 어려운 퍼즐

그림 3: 이건 행운을 빈다!