Binary Tree Shortest Path

This problem involves a special "binary tree" where each node has two children. The height of the node is defined as follows: if a parent node has height \(h\), then both of its children have height \(h+1\). All nodes having the same height form a layer. Moreover, every node's left child's subtree lies entirely to the left of its right child's subtree, and adjacent nodes in any layer are connected by an edge.

We represent a path in the tree by a string in which each character denotes a move. The allowed moves are:

• 1: move to the left child. (If the current node is at layer \(h\) with position \(i\), its left child is at layer \(h+1\) with position \(2\times i\).)
• 2: move to the right child. (The right child is at layer \(h+1\) with position \(2\times i + 1\).)
• U: move to the parent. (The parent of a node at \((h,i)\) is at layer \(h-1\) with position \(\lfloor i/2 \rfloor\).)
• L: move to the node immediately to the left on the same layer. (Guaranteed that the current node is not the leftmost node on its layer.)
• R: move to the node immediately to the right on the same layer. (Guaranteed that the current node is not the rightmost node on its layer.)

Each given path string indicates the endpoint achieved after performing the moves from the root (which is at layer \(0\) and position \(0\)). For example, the path 221LU leads to a certain node (say, node A in the reference diagram).

Your task is: given two path strings, determine the length of the shortest path (in terms of number of moves along the tree edges) between the two endpoints. Note that the tree edges include both vertical parent-child edges and horizontal edges connecting consecutive nodes on the same layer.

Hint: If a node's coordinate is represented as \((h,i)\) (where \(h\) is the layer and \(i\) is the position in that layer), then note that when moving upward \(h-L\) layers, the position becomes \(\lfloor i / 2^{(h-L)} \rfloor\). Using this observation, you may consider trying all possible common layers \(L\) to meet and computing the distance as:

[ \text{distance} = (h_1 - L) + (h_2 - L) + \left| \left\lfloor \frac{i_1}{2^{(h_1-L)}} \right\rfloor - \left\lfloor \frac{i_2}{2^{(h_2-L)}} \right\rfloor \right| ]

inputFormat

The input consists of two lines. Each line is a non-empty string containing only the characters 1, 2, U, L, and R, representing a path from the root.

outputFormat

Output a single integer, which is the minimum number of moves needed to travel from the endpoint of the first path to the endpoint of the second path.

sample

1
2

1