유전학

최근 뉴멕시코의 어느 분화구 근처에서 외계 박테리아 군집이 발견되었습니다. 파우처 박사는 ICPC 바이오랩에서 외계 DNA 구조를 연구하는 과학팀을 이끌고 있습니다. 이들의 발견을 아래에 간략히 정리합니다.

외계 DNA 분자는 뉴클레오타이드로 이루어진 원형 수열의 구조를 가집니다. 뉴클레오타이드는 26가지 종류가 있으며, 각각은 두 가지 면으로 나타날 수 있습니다. 중요한 점은, 어떤 외계 DNA 분자에서든 각 뉴클레오타이드는 아예 나타나지 않거나 정확히 두 번 나타난다는 것입니다(따라서 분자의 길이는 2 이상 52 이하의 짝수입니다). 어떤 뉴클레오타이드가 두 번 나타날 때, 두 번의 등장은 각각 독립적으로 어느 면이든 될 수 있습니다. 외계 박테리아에는 두 종류의 말단이 있는데, 전문 용어로 각각 팔(arm)과 다리(leg)라고 부릅니다. 파우처 박사 팀의 큰 성과는 DNA 구조만 보고 박테리아의 팔과 다리의 정확한 개수를 알아내는 방법을 찾은 것입니다.

여기서는 각 뉴클레오타이드를 알파벳 한 글자로 나타냅니다. 뉴클레오타이드를 $a, A, \dots, z, Z$로 적으며, 한 글자의 소문자와 대문자는 그 뉴클레오타이드가 가질 수 있는 두 면을 뜻합니다. 또한 면을 특정하지 않고 뉴클레오타이드를 가리킬 때는 $a/A, b/B, \dots, z/Z$로 적습니다.

말단의 개수를 알아내기 위해, 파우처 박사는 팔과 다리 두 개의 계수기를 0으로 초기화한 뒤, 수열을 다른 수열로 바꾸는 수술을 여러 번 시행합니다. 각 변환 뒤에는 적용한 수술에 따라 계수기 중 하나를 늘려야 할 수 있습니다. 빈 수열($\emptyset$로 표기)에 도달하면 원래 분자의 말단 개수를 구한 것입니다. 가능한 수술은 다음과 같습니다.

서로 반대 면으로 나타난 같은 뉴클레오타이드의 연속된 두 등장을 제거합니다. 팔과 다리의 수는 그대로 유지됩니다. 예를 들어 aBbCaC에서 Bb를 제거하면 aCaC가 되고, DeHhEd에서 dD를 제거하면 eHhE가 됩니다. DNA는 원형이므로 문자열 표현에서 마지막 글자와 첫 글자는 서로 이웃합니다.
같은 면으로 나타난 같은 뉴클레오타이드의 연속된 두 등장을 제거합니다. 팔의 수에 1을 더합니다. 예를 들어 BBcgCg에서 BB를 제거하면 cgCg가 되고, xabyyaBX에서 yy를 제거하면 xabaBX가 됩니다.
서로 다른 두 뉴클레오타이드가 번갈아 나타나고 각 뉴클레오타이드의 두 등장이 서로 반대 면인, 네 개의 뉴클레오타이드를 제거합니다. 다리의 수에 1을 더합니다. 예를 들어 dcDCefFe에서 dcDC를 제거하면 efFe가 되고, cmNMnC에서 mNMn을 제거하면 cC가 됩니다.
자르고 붙이기. 가장 복잡한 절차입니다. 먼저 뉴클레오타이드 하나(예: $a/A$)를 고르고, 그 뉴클레오타이드가 각 조각에 한 번씩 들어가도록 원형 수열을 두 개의 선형 사슬로 자릅니다. 다음으로, $a/A$의 두 등장이 같은 면이라면 한 조각을 뒤집습니다. 즉 순서를 거꾸로 하고 그 조각 안 모든 뉴클레오타이드의 면을 반대로 바꿉니다. 그런 다음 $a$ 앞의 부분과 $A$ 뒤의 부분을, 그리고 $a$ 뒤의 부분과 $A$ 앞의 부분을 이어 붙여 두 사슬을 합칩니다. 마지막으로 새로운 $a/A$ 뉴클레오타이드 두 개를 더해 사슬을 원형으로 닫습니다. 원래 고른 쌍이 같은 면이었으면 새 두 뉴클레오타이드도 같은 면이고, 아니면 서로 다른 면입니다. 형식적으로, $a/A$가 두 번 모두 면 $a$(또는 두 번 모두 면 $A$)로 나타나면, 이 수술은 $S_1 a S_2 S_3 a S_4$(각각 $S_1 A S_2 S_3 A S_4$) 형태의 수열을 $S_2 a S_1 \bar{S}_3 a \bar{S}_4$(각각 $S_2 A S_1 \bar{S}_3 A \bar{S}_4$)로 바꿉니다. 여기서 $\bar{S}$는 뒤집은 사슬을 뜻합니다. 반대로 $a/A$가 서로 다른 두 면으로 나타나면, $S_1 a S_2 S_3 A S_4$를 $S_2 a S_1 S_4 A S_3$로 바꿉니다. $S_1, S_2, S_3, S_4$는 (비어 있을 수도 있는) 임의의 부분 사슬이며, 원래 원형 사슬은 $S_1 (a/A) S_2$와 $S_3 (a/A) S_4$로 잘렸습니다. 예를 들어 BacDcAbD에서 사슬 BacDc와 AbD를 잘라 내고 $a/A$에서 합치면 cDcaBbDA가 되며, 마지막의 a와 A가 새로 더한 두 뉴클레오타이드이고 $S_1 = $ B, $S_2 = $ cDc, $S_3 = \emptyset$, $S_4 = $ bD입니다. 또 다른 예로, 같은 BacDcAbD를 DBac와 DcAb로 자르고 $c/C$에서 붙이면(이 경우 한 사슬을 뒤집어야 하며, 예를 들어 BaCd) cDBadcBa가 되고 $S_1 = $ DBa, $S_2 = \emptyset$, $S_3 = $ D, $S_4 = $ Ab입니다. 이 수술은 팔이나 다리의 수를 바꾸지 않지만, 앞의 수술들과 함께 영리하게 사용하면 분자의 크기를 줄여 계산을 끝낼 수 있습니다.

그런데 외계 박테리아는 팔과 다리를 동시에 가지지 않습니다. 발달 초기에, 팔이 하나라도 있으면 다리는 두 개의 팔로 바뀌기 때문입니다. 그래서 최종 결과는 팔의 수이거나 다리의 수이며, 둘이 동시에 나오지는 않습니다. 값비싼 수술을 피하기 위해 파우처 박사는 여러분에게 DNA 수열이 주어졌을 때 박테리아가 갖게 될 팔과 다리의 수를 계산하는 프로그램을 의뢰했습니다. 그 결과는 적용하는 수술의 순서와 무관하게 원래 문자열에 의해 유일하게 결정됨이 보장됩니다.

문제

입력

출력