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

---

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

دریایی که کِوین در آن قرار دارد جدولی از چهار طرف نامتناهی است، ولی ما تنها در مورد یک زیرجدول $n$ در $m$ از آن اطلاع داریم و می‌دانیم که بجز خشکی‌های داخل این زیر‌جدول، ‌در این دریا خشکی دیگری وجود ندارد.

برای درک بهتر مسأله‌ی او ابتدا تعاریف مورد نیاز مساله‌اش را بیان می‌کنیم:

• خانه‌های مجاور هر خانه تمام خانه‌هایی اند که حداقل یک را‌ٔس مشترک با‌ آن دارند. هر خانه در جدول ۸ خانه مجاور دارد.
• جزیره به مجموعه‌ای ماکسیمال (یعنی هیچ خانه‌ی خشکی‌ای وجود ندارد که مجاور حداقل یکی از خانه‌های آن باشد و عضوی‌ از مجموعه نباشد) از خانه‌های خشکی است که همبند (بین هر دو خانه‌ای از آن مسیری شامل خانه‌های خشکی وجود دارد) است.
• یک مسیر دریایی به دنباله‌ای از خانه‌های آبِ مجاور گفته‌ می‌شود که دو خانه‌ی خشکی را به هم وصل می‌کنند.
• اگر بین دو جزیره یک مسیر دریایی وجود داشته باشد آن دو جزیره دوست دریایی یکدیگر نامیده می‌شوند.
• به دنباله‌ای از تعدادی جزیره دو به دو متمایز که هر دو جزیره متوالی از آن دوست دریایی یکدیگر باشند مسافرت گفته می‌شود.

کِوین می‌خواهد از هر کدام از جزیره‌های این دریا دقیقا یک‌بار دیدن بکند و تمام کالاهای موجود را جمع‌آوری کند. او می‌خواهد که این کار در کمترین تعداد مسافرت ممکن انجام شود. به او کمک کنید که این مسئله‌ را حل کند.

ورودی

ورودی شامل یک خط است که در آن دو عدد طبیعی $n$ و $m$ با فاصله از هم آمده است. $$1 \le n,m \le 1 \ 000$$ سپس یک جدول $n$ در $m$ که از . یا # تشکیل شده است داده می‌شود. . نشان دهنده آب و # نشان دهنده خشکی است.

خروجی

در تنها خط خروجی تعداد مسافرتهای لازم را خروجی‌‌دهید.

مثال

ورودی نمونه ۱

5 5
#.#.#
..#..
#####
..#..
#.#.#

خروجی نمونه ۱

1

توضیح: $*$ مسیر مسافرت را نشان می‌دهند:

.........
..***....
..#.#*#*.
....#..*.
..#####*.
....#..*.
..#.#*#*.
..****...
.........

ورودی نمونه ۲

7 17
###############.#
#.#####.#####.#..
#.#...#.#...#.#..
#.#.#.#.#.#.#.#..
#.#...#.#...#.#..
#.#####.#####.#..
###############..

خروجی نمونه ۲

2

توضیح: $*$ مسیر مسافرت را نشان می‌دهند:

.....................
.....................
..###############*#*.
..#.#####.#####.#....
..#.#.*.#.#...#.#....
..#.#.#.#.#.#*#.#....
..#.#...#.#...#.#....
..#.#####.#####.#....
..###############....
.....................
.....................