Thanh tẩy

Bạn đang đứng trong một căn phòng hình vuông gồm $N\times N$ ô, các hàng được đánh số từ $1$ đến $N$ từ trên xuống dưới, các cột được đánh số từ $1$ đến $N$ từ trái sang phải. Ban đầu mọi ô đều bị nhiễm tà khí và bạn phải thanh tẩy toàn bộ chúng.

Cách duy nhất để thanh tẩy là niệm chú "Thanh Tẩy" lên một ô. Khi niệm chú lên ô $(i,j)$, tất cả các ô nằm cùng hàng $i$ và tất cả các ô nằm cùng cột $j$ sẽ được thanh tẩy (kể cả chính ô $(i,j)$). Một ô có thể được thanh tẩy nhiều lần.

Tuy nhiên, một số ô bị nhiễm tà khí quá nặng: bạn không thể niệm chú lên các ô đó, ngay cả sau khi chúng đã được thanh tẩy. Chúng vẫn có thể được thanh tẩy gián tiếp nếu một ô cùng hàng hoặc cùng cột với chúng được chọn để niệm chú.

Hãy tìm cách thanh tẩy toàn bộ $N\times N$ ô với số lần niệm chú ít nhất, hoặc cho biết điều đó là không thể.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $N$.
• $N$ dòng tiếp theo, mỗi dòng chứa $N$ ký tự mô tả lưới. Ký tự thứ $j$ của dòng thứ $i$ là E nếu ô $(i,j)$ là ô nhiễm nặng (không thể niệm chú lên), và . nếu ngược lại.

Dữ liệu ra

Nếu không có cách nào thanh tẩy toàn bộ lưới, in ra $-1$.

Ngược lại, gọi $x$ là số lần niệm chú ít nhất. In ra $x$ dòng, dòng thứ $k$ chứa hai số nguyên là chỉ số hàng và chỉ số cột của ô được niệm chú ở lần thứ $k$. Nếu có nhiều đáp án cùng dùng $x$ lần niệm chú, in ra đáp án bất kỳ.

Ràng buộc

• $1\le N\le 100$
• Mỗi ký tự của lưới là E hoặc .

Ví dụ