题目描述

题目译自 CEOI2013 Day2 T1「Board」

Mirko 和 Slavko 有一个新的棋盘游戏。游戏棋盘类似于一棵完整的无限二叉树。更准确地说，棋盘由节点和连接它们的双向道路组成。根节点位于棋盘的顶部，我们称其为第零层。每个节点恰好有两个子节点，左子节点和右子节点，分别位于父节点的左下方和右下方。子节点的层级比父节点高一级。除了连接父节点与其子节点的道路外，每一层的所有节点之间也都有道路连接：从最左边的节点开始，每个节点与同一层中其右侧的下一个节点相连。

通过棋盘的每条路径都是一系列操作，每一步通过一条道路从一个节点移动到另一个不同的节点。每一步可以用一个字符来描述，具体如下：

• 字符 1 表示从当前节点移动到其左子节点，
• 字符 2 表示从当前节点移动到其右子节点，
• 字符 U 表示从当前节点移动到其父节点，
• 字符 L 表示从当前节点移动到同一层中左侧的下一个节点，
• 字符 R 表示从当前节点移动到同一层中右侧的下一个节点。

例如，如果我们从根节点开始，按照步骤序列 221LU，我们将到达图中标记为字母 A 的节点。

请编写一个程序，给定棋盘上的两个节点，找到从一个节点到另一个节点所需的最少步骤数。这两个节点通过从根节点到它们各自的路径来指定。如果这两个路径指向同一个节点，答案为零。

输入格式

第一行的输入包含一个字符串，表示从根节点到第一个节点的路径。

第二行的输入包含一个字符串，表示从根节点到第二个节点的路径。

这两条路径都是有效的（即序列中的每一步都是可以执行的移动）。

输出格式

输出一行包含一个整数 ，从一个节点移动到另一个节点所需的最少步数。

111RRRRRRR
222

0

221LU
12L2

3

11111
222222

10

数据范围与提示

设 $D$ 为两个输入路径中访问的所有节点所在层数的最大值。

• 对于 $20\%$ 的测试数据，$D$ 最多为 $10$。
• 对于 $40\%$ 的测试数据，$D$ 最多为 $50$。
• 对于 $70\%$ 的测试数据，$D$ 最多为 $1000$。
• 对于 $100\%$ 的测试数据，输入的两个字符串长度均不超过 $10^5$。