SPOJ in Armenian

Տրված է n x m դաշտ, որը բաղկացած է դատարկ վանդակներից և պատերից: Դաշտի վրա գտնվում են երկու ռոբոտներ՝ A-ն և B-ն: Ամեն քայլի ընթացքում երկու ռոբոտներից մեկ կամ երկուսը կարող են տեղաշարժվել հարևան վանդակներից մեկը: Շարժվել կարելի է նաև անկյունագծով: Ռոբոտները չեն կարող քայլել պատերի վրայով կամ դուրս գալ դաշտի սահմաններից: Ինչպես նաև ռոբոտները չեն կարող որևէ  քայլի վերջում զբաղեցնել միևնույն վանդակը: Ռոբոտներին արգելվում է ինչ որ քայլի ընթացքում փոխանակել իրենց զբաղեցրած վանդակները: Սակայն ռոբոտներից մեկը կարող է գնալ այն վանդակը, որը քայլից առաջ զբաղեցնում էր մյուս ռոբոտը: Պահանջվում է գտնել քայլերի նվազագույն քանակը, որոնց արդյունքում A ռոբոտը կհայտնվի  B-ի սկզբնական վանդակում, իսկ B-ն A-ի սկզբնական վանդակում:

Մուտքը

Մուտքի առաջին տողում տրված են n և m թվերը(1 <= n <= 50, 2 <= m <= 50)։ Հաջորդ n տողերից յուրաքանչյուրը պարունակում է m սիմվոլ, որոնք նկարագրում են դաշտը: Դատարկ վանդակները նշված են .-ով, իսկ պատերը X-ով: A-ի սկզբնակետում գրված է A, B-ի սկզբնակետում գրված է B:

Ելքը

Ելքում հարկավոր է արտածել պահանջվող քայլերի նվազագույն քանակը և -1, եթե ռոբոտները չեն կարող հասնել վերջնական դիրքին:

Օրինակներ

Մուտքը.
4 4
AB.X
XXX.
...X
.XXX

Ելքը.
11

Մուտքը.
2 2
AB
..

Ելքը.
2

Մուտքը.
1 3
A.B

Ելքը.
-1