- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
یک صفحه شطرنج به صورت یک جدول \(n \times m\) داریم. سطرهای آن به ترتیب از بالا به پایین با اعداد \(1\) تا \(n\) و ستونهای آن به ترتیب از چپ به راست با اعداد \(1\) تا \(m\) شماره گذاری شده است.
هر خانه از این جدول یا مانع دارد و یا آزاد است. میخواهیم \(k\) مهرهی فیل در خانههای خالی این جدول قرار دهیم، به طوری که هیچ دو فیلی یکدیگر را تهدید نکنند. دو فیل زمانی یک دیگر را تهدید میکنند که یک مسیر اریب و بدون مانع بین آنها موجود باشد.
از شما میخواهیم با دریافت وضعیت جدول، حداکثر تعداد فیلی که میتوان در این جدول گذاشت تا هیچ دو فیلی یکدیگر را تهدید نکنند را محاسبه کنید. همچنین یک وضعیت برای قرار دادن فیلها در جدول ارائه کنید. اگر چند پاسخ برای این مسئله وجود دارد، یکی را به دلخواه چاپ کنید.
ورودی
در خط اول به ترتیب دو عدد \(n\) و \(m\) میآید که نشان دهنده ابعاد جدول است.
\[1 \le n,m \le 400\]
در \(n\) خط بعد در هر خط یک رشته به طول \(m\) متشکل از . و # میآید. اگر حرف \(j\)ام رشته \(i\)ام # باشد یعنی خانهی سطر \(i\)ام و ستون \(j\)ام با مانع پر شده است و در غیر ایصورت اگر . باشد یعنی آن خانه خالی است.
خروجی
در سطر اول خروجی، عدد صحیح \(k\) که نشاندهندهی حداکثر تعداد فیل است را چاپ کنید.
در \(k\) سطر بعدی، در هر سطر دو عدد صحیح \(r_i\) و \(c_i\) که با یک فاصله از هم جدا شدهاند و به ترتیب نشاندهندهی شمارهی سطر و ستون فیل \(i\)ام است را چاپ کنید.
مثالها
ورودی نمونه ۱
4 11
...#..#....
.#.##.#....
...#.##....
####..#....
خروجی نمونه ۱
16
1 1
1 3
1 5
1 6
1 8
1 9
1 10
2 1
2 3
3 1
3 3
3 5
4 5
4 8
4 9
4 10
خانههای سفید خالی، خانههای سیاه مانع و خانههای سبز فیل هستند.
ورودی نمونه ۲
10 10
.....#....
.#......#.
.#...#....
.....#....
..........
#....#.#..
.........#
#......#..
...#...#..
.....#....
خروجی نمونه ۲
27
1 1
1 3
1 4
1 8
1 9
1 10
2 1
3 1
3 3
3 10
4 1
4 3
4 7
4 10
5 7
5 10
6 10
7 1
7 2
7 7
8 4
8 9
8 10
9 1
10 3
10 9
10 10
