消消乐
题号:NC20644
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

r神在和小b比赛玩一个名为“消消乐”的游戏,在一个n*m的棋盘上,一些棋子分布在格点上,游戏玩家有一个名为超蓝光波的武器,可以消除一行或者一列的所有棋子,使用超蓝光波需要耗费一点能量,消除完所有的棋子之后,花费能量越少得分越高。
r神为了超过排名第一的小b,夺得荣誉称号“天下第一”,他需要寻求你的帮助,他希望知道最少需要使用多少次“超蓝光波”,以及在哪行、哪列使用。

输入描述:

第一行两个正整数n(n<=2000),m(m<=2000);

接下来n行,每行m个字符,表示棋盘,其中“.”表示该处没有棋子,“*”表示该处有棋子,棋子个数<=100000

输出描述:

第一行输出一个正整数,表示最少需要使用的“超蓝光波”次数

第二行N+1个正整数,第一个数为N,表示需要消掉的行数,从小到大输出每个需要消除的行号

第三行M+1个正整数,第一个数为M,表示需要消掉的列数,从小到大输出每个需要删除的列号

如果有多种情况,任意输出一种即可。
示例1

输入

复制
3 4
.*..
**.*
.*..

输出

复制
2
1 2
1 2
示例2

输入

复制
3 4
.*..
**.*
..*.

输出

复制
3
3 1 2 3 
0