게임판 Batch 컴파일 명령

승현이와 지학이는 새로운 보드 게임을 개발해 냈습니다. 정보를 굉장히 좋아하는 둘답게 게임판은 완전 이진 트리의 형태를 띠고 있습니다. 판이 어떻게 생겼는지 정확하게 설명하자면, 게임판은 노드들과 이들을 연결하는 양방향 간선들로 구성되어 있습니다. 루트 노드는 게임판의 맨 위에 위치해 있으며 이 노드는 레벨 0에 있다고 말할 수 있습니다. 각 노드는 좌측 자식 노드와 우측 자식 노드, 이렇게 정확히 두 개의 자식 노드를 가집니다. (좌측 자식 노드는 부모 노드의 좌측 하단에, 우측 자식 노드는 부모 노드의 우측 하단에 위치합니다.) 자식 노드의 레벨은 부모 노드의 레벨보다 정확히 1 더 큽니다. 이제 이렇게 구성한 노드들을 연결하는 간선들을 설치합니다. 부모 노드와 자식 노드 간에는 간선이 반드시 연결되어 있고, 같은 레벨 상에 있는 모든 노드들에 대해, 레벨이 같고 자신의 오른쪽에 있는 가장 가까운 노드가 존재한다면 자신과 그 노드를 연결합니다.

[그림 1] 두 번째 입력 예제

게임판에서 경로란 한 노드에서 다른 노드로 이동하는 일련의 과정들을 나열한 것을 말합니다. 한 노드에서 다른 노드로 이동하는 과정은 아래와 같이 한 글자의 문자로 표현할 수 있습니다.

• '1' : 왼쪽 자식 노드로 이동
• '2' : 오른쪽 자식 노드로 이동
• 'U' : 부모 노드로 이동
• 'L' : 같은 레벨에 있고 자신보다 왼쪽에 위치한 노드들 중에서 가장 가까운 노드로 이동
• 'R' : 같은 레벨에 있고 자신보다 오른쪽에 위치한 노드들 중에서 가장 가까운 노드로 이동

예로 들어 승현이가 루트 노드에서 시작하여 '221LU'의 과정을 밟았다면 승현이는 [그림 1]에서 'A'로 표시된 노드에 도착하게 됩니다.

해야 할 일

게임판에 있는 두 개의 노드가 주어질 때, 한 노드에서 다른 노드로 갈 수 있는 모든 경로들 중에서 가장 짧은 것의 길이를 구하는 프로그램을 작성하세요. 두 노드는 루트 노드에서부터 시작하는 경로로 주어집니다. 만약 주어진 두 경로를 따라 이동했을 때 도착한 노드가 서로 같다면, 0을 출력해야 합니다.

입력 형식

첫 번째 줄에는 최대 10만 글자로 구성된 경로 하나가 주어집니다. 이 경로를 따라 이동하면 1번 노드에 도착하게 됩니다.

두 번째 줄에는 최대 10만 글자로 구성된 또다른 경로 하나가 주어집니다. 이 경로를 따라 이동하면 2번 노드에 도착하게 됩니다.

주어진 두 경로는 실제로도 이동 가능한 경로임이 보장됩니다.

출력 형식

첫 번째 줄에 1번 노드에서 2번 노드로 갈 수 있는 경로들 중에서 가장 짧은 것의 길이를 출력합니다. ('짧다'는 것은 그 길이가 짧다는 것을 의미합니다.)

채점 기준

주어지는 두 경로를 따라 이동했을 때 방문하는 가장 레벨이 큰 노드의 레벨을 $D$로 둡니다.

• 20점에 해당하는 테스트 데이터에 대해 $D$는 최대 10입니다.
• 40점에 해당하는 테스트 데이터에 대해 $D$는 최대 50입니다.
• 70점에 해당하는 테스트 데이터에 대해 $D$는 최대 1000입니다.

제출 시 피드백

대회 중에 여러분은 답안을 최대 50번까지 제출할 수 있으며, 제출한 답안은 공식 데이터 중 일부로 채점됩니다. 채점이 완료되면 대회 시스템에서 간략한 정보를 찾아볼 수 있습니다.

입출력 예제