题目描述

一个 $n \times m$ 的棋盘上有若干位置被放上棋子，需要在部分空位上放上棋子，使得存在唯一的在棋子间两两匹配的方案，满足每对棋子在同一行或同一列。

请你求出额外添加的棋子数的最小值，或报告无解。

输入格式

第一行两个整数 $n$，$m$，表示棋盘大小。

接下来 $n$ 行，每行一个长为 $m$ 的字符串，第 $i$ 行的第 $j$ 个字符表示位置 $(i, j)$ 的状态：

• 若其为 .，表示没有棋子，
• 若其为 #，表示有棋子。

输出格式

输出一行一个整数。$-1$ 表示无解，否则表示最少添加的棋子数。

输入样例1

2 3
###
...

输出样例1

1

输入样例2

1 3
...

输出样例2

0

输入样例3

2 4
#.##
.#.#

输出样例3

-1

输入样例4

9 10
....#.....
.....#....
......#...
..#.......
...#......
#....#....
..........
.#........
.......#..

输出样例4

7

数据范围

对于所有测试点，$1 \leq n, m \leq 10^3$，每个字符都在 .# 中。。

• 子任务 1（15 分）：$1 \leq n, m \leq 3$，
• 子任务 2（10 分）：$1 \leq n, m \leq 10$，初始时没有两个棋子在同一行或同一列，
• 子任务 3（30 分）：$1 \leq n, m \leq 10$，
• 子任务 6（45 分）：无特殊限制。