B. Мемори и трезубец
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мемори гуляет по декартовой плоскости, начиная в точке начала координат. У неё есть последовательность действий s:

  • Символ «L» означает шаг на единицу влево.
  • Символ «R» означает шаг на единицу вправо.
  • Символ «U» означает шаг на единицу вверх.
  • Символ «D» означает шаг на единицу вниз.

Мемори хочет, чтобы, последовательно исполнив все команды, она снова оказалась в точке начала координат. У неё есть специальный трезубец, который за одно применение может изменить любой символ в строке s на один из символов «L», «R», «U» или «D». Однако пользоваться трезубцем нелегко, поэтому Мемори хочет минимизировать количество его применений или определить, что добиться желаемого невозможно в принципе.

Входные данные

В единственной строке входных данных записана строка s (1 ≤ |s| ≤ 100 000) — последовательность инструкций, которая есть у Мемори.

Выходные данные

Если невозможно изменить строку так, чтобы Мемори заканчивала путешествие в точке начала координат, то выведите -1 в единственной строке выходных данных. В противном случае выведите минимальное требуемое количество изменений.

Примеры
Входные данные
RRU
Выходные данные
-1
Входные данные
UDUR
Выходные данные
1
Входные данные
RUUR
Выходные данные
2
Примечание

В первом примере Мемори сначала идёт направо, потом снова направо, затем вверх. Можно показать, что эту последовательность инструкций невозможно изменить таким образом, чтобы она возвращала Мемори в начало координат.

Во втором примере Мемори сначала идёт вверх, потом вниз, потом вверх, потом направо. Одним из возможных решений является изменение строки s на «LDUR», для этого потребуется внести только одно изменение.