Board Game "Tree"

Wonseop and Sanghyun bought a board game. The board is an infinite binary tree made of nodes and two-way roads between them.

The root node sits at the very top of the board and its level is 0. Every node has one left child and one right child. The left child sits below and to the left of its parent, the right child below and to the right, and a child's level is one greater than its parent's level.

There are two kinds of roads. One kind joins a parent to a child. The other kind joins all the nodes on one level: it starts at the leftmost node of that level and links each node to the node on its right.

Taking one road moves you to a neighbouring node. There are five moves, each written with a single character.

• move to the left child: 1
• move to the right child: 2
• move to the parent: U
• move to the node immediately to the left on the same level: L
• move to the node immediately to the right on the same level: R

A run of such moves written in order is called a path. Following 221LU from the root goes down to the right child, the right child and the left child, then one step left on that level and one step up to the parent, which ends at the third node from the left on level 2.

Two nodes on the board are given. Write a program that finds the minimum number of moves needed to get from one node to the other. Each node is given as a path that starts at the root, and the answer is 0 when the two paths describe the same node.

The first line contains the path from the root to the first node. The second line contains the path from the root to the second node.

Neither path is longer than 100,000 characters, and both are always valid, so no move ever leads off the board.

Print the minimum number of moves needed to get from one node to the other.