← 返回题目列表

Codeforces · 712/B

B. 内存和三叉戟

中文机器翻译题面 查看原题

记忆正在二维平面上从原点开始行走。给他一个字符串 s ,其中包含他的运动方向:

- “L”表示他应该向左移动一个单位。
- “R”表示他应该向右移动一个单位。
- “U”表示他应该向上移动一个单位。
- “D”表示他应该向下移动一个单位。

但现在记忆想要在原点结束。为此,他有一把特殊的三叉戟。此三叉戟可以将 s 中的任何字符替换为“L”、“R”、“U”或“D”中的任何一个。然而,因为他不想磨损三叉戟,所以他希望尽可能减少编辑次数。请告诉记忆,他需要进行的最少更改次数是多少,才能产生一个在行走时将在原点结束的字符串,或者如果不存在这样的字符串。

输入

第一行也是唯一一行包含字符串 s (1 ≤ |s| ≤ 100 000) — 给出了 Memory 指令。

输出

如果有满足条件的字符串,则输出一个整数——所需的最小编辑次数。如果无法以将内存带回原点的方式更改序列,则输出 -1。

示例

输入 #1

RRU

输出 #1

-1

输入 #2

UDUR

输出 #2

1

输入 #3

RUUR

输出 #3

2

注意

在第一个示例测试中,内存被告知先向右走,然后向右走,然后向上走。很容易看出,编辑这些指令来形成有效的行走是不可能的。

在第二个示例测试中,内存被告知向上走,然后向下走,然后向上走,然后向右走。一种可能的解决方案是将 s 更改为“LDUR”。该字符串使用了 1 次编辑,这是可能的最小值。它也结束于原点。