Uolevi on pysäköinyt autonsa parkkipaikalle. Hän haluaa ajaa autonsa pois parkkipaikalta, mutta se ei ole aivan helppoa: parkkipaikka on aivan kaaoksessa, koska jotkut ovat pysäköineet autonsa väärin paikkoihin. Uolevin auton peruutusvaihde on rikki ja tietenkään autolla ei voi kääntyä aivan paikallaan.

Parkkipaikka on ruudukko, jonka ruudut ovat joko vapaita tai sisältävät esteitä. Uolevin auto on aluksi jossain ruudukon vapaassa ruudussa, ja sen suunta on ylöspäin. Jokaisella siirrolla Uolevi joko kääntää auton suuntaa 45° vasemmalle tai oikealle tai pitää saman suunnan, ja siirtyy eteenpäin nykyiseen suuntaan yhden askeleen. Auto ei missään vaiheessa saa päätyä esteruutuun. Uolevi pääsee ulos parkkipaikalta, mikäli hän pääsee johonkin ruutuun ruudukon reunalla.

Tehtävänäsi on etsiä vähiten siirtoja sisältävä reitti ruudukon reunaan.

Syöte

Syötteen ensimmäisellä rivillä on luvut n ja m, ruudukon korkeus ja leveys.

Seuraavat n riviä sisältävät ruudukon rivit, jotka ovat merkeistä #, . ja U muodostuvia merkkijonoja, joiden pituus on m. Merkillä # merkityt kohdat ovat esteitä, kaikista muista kohdista voi ajaa. Uolevin auto on aluksi kohdassa, joka on merkitty kirjaimella U, joita on tasan yksi ruudukolla.

Tuloste

Tulosta lyhimmän ruudukon reunaan päättyvän reitin pituus siirtoina.

Rajat

• 3 \leq n, m \leq 100

Voit olettaa, että jokin reitti ulos on olemassa.

Esimerkki

Syöte:

7 7
#######
#....##
#.#.#.#
#..##.#
##..U..
..###.#
.....##

Tuloste:

12

Selitys:
Aluksi Uolevin auton suunta on suoraan ylöspäin. Optimaalisen reitin 12 askelta ovat suuntiin YO, Y, YV, V, V, AV, A, AO, O, O, O, O (missä A = alas, Y = ylös, V = vasemmalle, O = oikealle). Reitti kelpaa, koska peräkkäisten askelten suunnat eroavat korkeintaan 45°. Huomaa, että reitti palaa lähtöruutuun - Uolevi ei voi lähteä suoraan oikealle, vaan ainoastaan suuntiin Y, YV tai YO. Reitti käy läpi X:llä merkityt ruudut (lähtöpisteessä käydään kahdesti):

#######
#.XXX##
#X#.#X#
#X.##X#
##XXXXX
..###.#
.....##