Мемори гуляет по декартовой плоскости, начиная в точке начала координат. У неё есть последовательность действий s:
- Символ «L» означает шаг на единицу влево.
- Символ «R» означает шаг на единицу вправо.
- Символ «U» означает шаг на единицу вверх.
- Символ «D» означает шаг на единицу вниз.
Мемори хочет, чтобы, последовательно исполнив все команды, она снова оказалась в точке начала координат. У неё есть специальный трезубец, который за одно применение может изменить любой символ в строке s на один из символов «L», «R», «U» или «D». Однако пользоваться трезубцем нелегко, поэтому Мемори хочет минимизировать количество его применений или определить, что добиться желаемого невозможно в принципе.
Выходные данные
Если невозможно изменить строку так, чтобы Мемори заканчивала путешествие в точке начала координат, то выведите -1 в единственной строке выходных данных. В противном случае выведите минимальное требуемое количество изменений.
Примечание
В первом примере Мемори сначала идёт направо, потом снова направо, затем вверх. Можно показать, что эту последовательность инструкций невозможно изменить таким образом, чтобы она возвращала Мемори в начало координат.
Во втором примере Мемори сначала идёт вверх, потом вниз, потом вверх, потом направо. Одним из возможных решений является изменение строки s на «LDUR», для этого потребуется внести только одно изменение.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
RRU
|
-1
|
|
2
|
UDUR
|
1
|
|
3
|
RUUR
|
2
|