Phủ Các Ô Được Đánh Dấu · canuc80k6404

Một bảng vuông gồm $N$ hàng và $N$ cột. Mỗi ô hoặc để trống, hoặc được đánh dấu bằng ký tự $o$ .

Bạn được chọn một số hàng và một số cột. Một ô đánh dấu được phủ khi hàng của nó hoặc cột của nó được chọn. Hãy phủ mọi ô đánh dấu bằng ít đường nhất và đưa ra một phương án tối ưu.

Các hàng và cột đều được đánh số từ $1$ đến $N$ .

Input

Dòng đầu chứa số nguyên $N$ .
$N$ dòng tiếp theo, mỗi dòng là một chuỗi gồm đúng $N$ ký tự:
. biểu thị ô trống;
$o$ biểu thị ô được đánh dấu.

Output

Dòng đầu in số nguyên $K$ : số hàng và cột được chọn. $K$ phải nhỏ nhất có thể.
Trong $K$ dòng tiếp theo, mỗi dòng in hai số nguyên:
$1$ $i$ nếu chọn hàng $i$ ;
$2$ $j$ nếu chọn cột $j$ .
Mỗi hàng hoặc cột chỉ được liệt kê nhiều nhất một lần. Có thể in bất kỳ phương án tối ưu nào.

Constraints

$1 \leq N \leq 100$ .
Mỗi dòng bảng chứa đúng $N$ ký tự thuộc tập {'.', 'o'}.
Bảng có thể không chứa ô đánh dấu nào.

Scoring

Subtask $1$ ( $50%$ số điểm): $N \leq 10$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

4
.o..
.o.o
...o
.o..

Output

2
2 2
2 4

Giải thích: Chọn cột $2$ và cột $4$ sẽ phủ cả năm ô được đánh dấu. Không thể chỉ chọn một đường vì có ô ở hàng $1$ , cột $2$ và một ô khác ở hàng $3$ , cột $4$ ; hai ô này không nằm chung hàng hoặc cột. Vì vậy $K = 2$ là tối ưu.

Mô hình đồ thị: Tạo một đỉnh trái cho mỗi hàng và một đỉnh phải cho mỗi cột. Mỗi ô o tại hàng i, cột j trở thành cạnh nối hai đỉnh tương ứng. Chọn hàng hoặc cột để phủ mọi ô chính là chọn một tập đỉnh phủ mọi cạnh.
Mô hình đồ thị: Trong đồ thị hai phía, định lý König cho biết kích thước vertex cover nhỏ nhất bằng kích thước matching lớn nhất.
Thuật toán: 1. Tìm maximum matching giữa các hàng và cột bằng Hopcroft-Karp. 2. Bắt đầu từ mọi hàng chưa được ghép. Duyệt các đường xen kẽ: từ hàng đi qua cạnh không thuộc matching; từ cột đi ngược qua cạnh thuộc matching. 3. Gọi Z_L là tập hàng tới được và Z_R là tập cột tới được. 4. In các hàng không thuộc Z_L và các cột thuộc Z_R.
Chứng minh tính đúng đắn: Tập (L \\ Z_L) ∪ Z_R phủ mọi cạnh. Thật vậy, nếu một cạnh có đầu hàng thuộc Z_L mà đầu cột không thuộc Z_R, quy tắc duyệt xen kẽ sẽ buộc cạnh đó là cạnh matching; khi ấy đầu hàng của nó chỉ có thể được tới từ chính đầu cột, gây mâu thuẫn với việc cột chưa được tới.
Chứng minh tính đúng đắn: Mỗi cạnh của matching góp đúng một đầu mút vào tập trên, nên kích thước tập bằng kích thước maximum matching. Mặt khác, mọi vertex cover phải chọn ít nhất một đầu của từng cạnh matching, do đó không thể nhỏ hơn matching. Tập được in vừa phủ mọi ô vừa đạt cận dưới này, nên là tối ưu.
Độ phức tạp: Có 2N đỉnh và nhiều nhất N² cạnh. Hopcroft-Karp chạy trong O(N²√N); bước truy vết tốn O(N²). Bộ nhớ là O(N²).