Masala #0628

Tap Away juda ajoyib o'yin bo'lib, uning qoidalari quyidagicha.

1. O'yin N×M maydonda bo'lib o'tadi. 

2. Maydondagi katakchalarga Tepaga, Pastga, Chapga, O'nga yo'nalishlari o'rnatilgan. Agar siz biron katakcha ustiga bossangiz va katakcha yo'nalishi bo'yicha yo'lakda bironta ham belgi bo'lmasa, katakcha o'ziga o'rnatilgan yo'nalish bo'yicha harakat qiladi, aks holda katakcha qimirlamaydi.

3. Siz istalgan katakchaga bosish orqali uni jadvaldan chiqarib yuborishingiz mumkin. Lekin buning uchun katakchaning yo'nalishidagi yo'lda boshqa katakcha bo'lmasligi kerak. Eslatib o'tamiz yo'lida to'siq bo'lmagan katakchani jadvaldan chiqarib yuborish bu bitta harakat hisoblanadi.

Siz jadvaldagi barcha katakchalarni o'yindan chiqarib yuborish uchun eng kamida nechta harakat qilish kerakligini toping.

Birinchi qatorda N va M butun sonlari beriladi.  ( 1 <= N,M <= 6)
Keyingi N ta qatorning har birida M tadan belgi probel bilan ajratilgan holda berilari: U-tepaga, D-pastga, L-chapga, R-o'ngga.

Barcha katakchalarni jadvaldan chiqarib yuborish uchun eng kamida nechta harakat qilish kerak. Agar buning imkoni bo'lmasa -1 chiqaring.