Problem Description

Consider the following “binary tree”:

• Each node has two children, left and right. The height of each node is defined as follows: if the height of a parent node is $h$, then the heights of both of its children are $h+1$. All nodes with the same height form one level.

• The subtree of a node’s left child is to the left of the subtree of its right child. Between every two adjacent nodes on the same level, there is an edge. An example is shown below:

Each path in the graph is represented by a string, where each character represents one move. The characters are only the following five types:

• $\tt 1$: move to the left child of the current node.
• $\tt 2$: move to the right child of the current node.
• $\tt U$: move to the parent of the current node.
• $\tt L$: move to the node on the same level immediately to the left of the current node (it is guaranteed that the current node is not the leftmost node on this level).
• $\tt R$: move to the node on the same level immediately to the right of the current node (it is guaranteed that the current node is not the rightmost node on this level).

A path denotes its endpoint. For example, the path $\tt 221LU$ denotes node $A$ in the figure above. Given two paths, your task is to find the shortest path length between the endpoints of these two paths.

Input Format

Two lines, each containing a string, representing the two paths.

Output Format

Output one line, the length of the shortest path between the two nodes.

221LU
12L2

3

111RRRRRRR
222

0

11111
222222

10

Hint

Let $D$ be the maximum depth among all nodes visited, and let $S$ be the maximum length of the input strings.

• For $10\%$ of the testdata, $D \leq 10$.
• For $30\%$ of the testdata, $D \leq 50$.
• For $50\%$ of the testdata, $D \leq 10^3$.
• For $70\%$ of the testdata, $D \leq 2 \times 10^4$.
• For $100\%$ of the testdata, $D \leq 10^5, S \leq 10^5$.

Input Format

Two lines, each containing a string, representing the two paths.

Output Format

Output one line, the length of the shortest path between the two nodes.

Translated by ChatGPT 5