시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 10 4 4 40.000%

문제

원섭이와 상현이는 보드 게임을 구매했다. 게임판은 무한 이진 트리와 비슷한 형태이다. 게임판은 노드와 노드를 연결하는 양방향 도로로 이루어져 있다.

루트 노드는 게임판의 가장 위에 있고, 이 노드의 레벨은 0이다. 모든 노드는 항상 두 자식을 가지며, 왼쪽 자식과 오른쪽 자식이다. 왼쪽 자식의 위치는 부모 노드의 왼쪽 아래이고, 오른쪽 자식의 위치는 오른쪽 아래이다. 자식 노드의 레벨은 부모 노드의 레벨보다 1 크다.

도로는 부모 노드와 자식 노드를 연결하는 도로가 있고, 같은 레벨에 있는 노드를 모두 연결하는 도로가 있다. 같은 레벨에 있는 노드를 모두 연결하는 도로는 각 레벨의 가장 왼쪽 노드에서 시작하며, 각각의 노드와 그 오른쪽에 있는 노드를 연결한다.

한 노드에서 도로를 한 번 이용해서 다른 노드로 이동할 수 있다. 이동은 다음과 같이 총 5가지가 있으며, 한 글자로 나타낼 수 있다.

  • 왼쪽 자식으로 이동: 1
  • 오른쪽 자식으로 이동: 2
  • 부모 노드로 이동: U
  • 같은 레벨의 바로 왼쪽에 있는 노드로 이동: L
  • 같은 레벨의 바로 오른쪽에 있는 노드로 이동: R

위와 같은 이동의 연속을 경로라고 한다.

예를 들어, 루트 노드에서 '221LU'로 이동한다면, A가 적힌 노드로 이동할 수 있다.

게임판 위의 두 노드가 주어진다. 이 때, 한 노드에서 다른 노드로 이동하는데 필요한 이동 횟수의 최소값을 구하는 프로그램을 작상하시오. 두 노드는 루트에서 이동한 경로로 주어지며, 두 경로가 같은 노드인 경우에 답은 0이다.

입력

첫째 줄에 루트에서 첫번째 노드로 이동하는 경로가 주어진다.

둘째 줄에 루트에서 두번째 노드로 이동하는 경로가 주어진다.

두 경로의 길이는 100,000을 넘지 않으며, 항상 올바른 경로이다. (즉, 이동할 수 없는 상황은 나타나지 않는다)

출력

첫째 줄에 한 노드에서 다른 노드로 이동하는데 필요한 이동 횟수의 최소값을 출력한다.

예제 입력

221LU
12L2

예제 출력

3

힌트

문제의 그림은 예제를 나타낸다.