یک جدول ‎$n \times m$‎ داریم که بعضی از خانه‌های آن سیاه‌اند و بعضی سفید. دو خانه مجاورند اگر هر دو سفید باشند و یا مجاور راسی باشند یا مجاور ضلعی. شما دو مهره در این جدول قرار داده‌اید و می‌خواهید با کم‌ترین تعداد حرکت جای این دو مهره را عوض کنید.

‎ شما می‌توانید در یک حرکت هر کدام از مهره‌ها را یا ثابت بگذارید یا به یک خانه مجاور آن ببرید به‌طوری‌که:

• در انتهای یک حرکت دو مهره در یک خانه قرار نداشته باشند.
• در یک حرکت جای دو مهره عوض نشود. یک مهره درصورتی می‌تواند به خانه مهره دیگر برود که در پایان حرکت، مهره دیگر در خانه‌ای غیر از خانه آن قرار داشته باشد.

شما باید برنامه‌ای بنویسید که با گرفتن ورودی کم‌ترین تعداد حرکت لازم برای جابه‌جا کردن مهره‌ها را به‌دست بیاورد.

• در سطر اول ورودی دو عدد ‎$1 \leq n \leq 20$‎ و ‎ $1 \leq m \leq 20$‎نشانگر تعداد سطرها و تعداد ستون‌ها جدول آمده است.
• در ‎$n$‎ سطر بعد، در هر یک $m$‎ کاراکتر آمده است که هر کدام از آن‌ها به یکی از صورت‌های زیر است.‎
  • ‎$X$‎ نشان‌دهنده یک خانه سیاه است‎.‎
  • ‎.‎ نشان‌دهنده یک خانه سفید است که در آن مهره‌ای نیست‎.‎
  • ‎$A$‎ نشان‌دهنده یک خانه سفید است که در آن مهره‌ی اول قرار دارد‎.‎
  • ‎$B$‎ نشان‌دهنده یک خانه سفید است که در آن مهره‌ی دوم قرار دارد‎.‎

در تنها سطر خروجی پاسخ سوال را چاپ نمایید. درصورتی‌که این کار امکان‌پذیر نبود در خروجی ‎$-1$‎ چاپ نمایید.‎

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل