보드 게임 "트리"

원섭이와 상현이가 보드 게임을 하나 샀다. 게임판은 무한히 뻗어 나가는 이진 트리 모양이고, 노드와 노드를 잇는 양방향 도로로 이루어져 있다.

루트 노드는 게임판의 가장 위에 있고 레벨이 0이다. 모든 노드는 왼쪽 자식과 오른쪽 자식을 하나씩 가진다. 왼쪽 자식은 부모의 왼쪽 아래에, 오른쪽 자식은 부모의 오른쪽 아래에 놓이고, 자식의 레벨은 부모의 레벨보다 1 크다.

도로는 두 종류다. 하나는 부모와 자식을 잇는 도로이고, 다른 하나는 같은 레벨의 노드를 모두 잇는 도로다. 두 번째 도로는 각 레벨의 가장 왼쪽 노드에서 시작해서 이웃한 두 노드를 차례대로 연결한다.

도로 하나를 지나면 이웃한 노드로 한 번 이동한다. 이동은 다섯 가지이고, 각각 한 글자로 나타낸다.

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

이런 이동을 차례대로 늘어놓은 것을 경로라고 한다. 루트에서 221LU를 따라가면 오른쪽 자식, 오른쪽 자식, 왼쪽 자식으로 세 번 내려간 다음 같은 레벨에서 왼쪽으로 한 칸 가고 부모로 한 칸 올라가서, 레벨 2의 왼쪽에서 세 번째 노드에 도착한다.

게임판 위의 두 노드가 주어진다. 한 노드에서 다른 노드로 가는 데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오. 두 노드는 루트에서 출발하는 경로로 주어지고, 두 경로가 같은 노드를 가리키면 답은 0이다.

첫째 줄에 루트에서 첫 번째 노드까지 가는 경로가 주어진다. 둘째 줄에 루트에서 두 번째 노드까지 가는 경로가 주어진다.

두 경로의 길이는 100,000을 넘지 않고, 항상 올바른 경로다. 즉 갈 수 없는 곳으로 이동하는 경우는 없다.

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