Bài toán này vốn sẽ là bài học lịch sử của Juan về IOI 1997 tại Nam Phi. Tuy nhiên, bài học đã bị các thành viên còn lại của ban tổ chức kiểm duyệt, nên đề bài sau đây đã đến tay bạn:

Abraham là một nhà thám hiểm dũng cảm, đi đến những nơi chưa lập trình viên nào từng đặt chân tới. Trong chuyến thám hiểm tiếp theo, anh dự định khám phá một mê cung rất kỳ lạ. Anh biết mê cung là một lưới $n \times n$ với một mũi tên ở mỗi ô. Mỗi mũi tên chỉ một trong bốn hướng: lên, xuống, trái hoặc phải. Nếu Abraham bước vào một ô, anh buộc phải đi theo các mũi tên bắt đầu từ ô đó. Mỗi mũi tên đưa Abraham đi một ô theo hướng nó chỉ; nếu đến một mũi tên chỉ ra ngoài mê cung, anh có thể thoát ra.

Abraham không biết các mũi tên trong mê cung hướng như thế nào, nhưng anh có thông tin khác. Trên bản đồ mê cung của anh, một số ô được tô đen và các ô khác được tô trắng. Anh tin rằng nếu bắt đầu ở bất kỳ ô đen nào, anh sẽ không bao giờ thoát khỏi mê cung, còn nếu bắt đầu ở bất kỳ ô trắng nào, cuối cùng anh sẽ thoát ra.

Giả định của Abraham có thể sai: có những cách bố trí ô đen và ô trắng mà các điều kiện đã nêu không thể đồng thời đúng với tất cả các ô, bất kể các mũi tên được định hướng thế nào. Hình sau cho thấy một ví dụ.

Bản đồ biểu diễn một mê cung mà các ô trắng có thể thỏa mãn giả định của Abraham. Nếu bắt đầu ở một trong hai ô đó, các mũi tên được vẽ sẽ dẫn anh ra khỏi mê cung, nhưng anh không thể bị mắc kẹt khi bắt đầu ở một ô đen, bất kể ta định hướng các mũi tên chưa được vẽ như thế nào.

Abraham nhờ bạn giúp xác định liệu với cách tô màu các ô trên bản đồ cho trước, có tồn tại một cách bố trí các mũi tên phù hợp với niềm tin của anh cho mọi ô trong lưới, cả đen lẫn trắng, hay không.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên dương $n$.
• Mỗi dòng trong $n$ dòng tiếp theo chứa $n$ ký tự, mỗi ký tự là 0 hoặc 1. 0 biểu thị ô đen và 1 biểu thị ô trắng. $n$ dòng này mô tả lưới.

Dữ liệu ra

In SI nếu có thể định hướng các mũi tên sao cho Abraham không bao giờ thoát ra khi bắt đầu ở ô đen, và cuối cùng thoát ra khi bắt đầu ở ô trắng.

In NO nếu điều đó là không thể.

Ví dụ

Dữ liệu vào 1

3
001
001
111

Dữ liệu ra 1

SI

Dữ liệu vào 2

2
01
10

Dữ liệu ra 2

NO

Ghi chú

Ví dụ thứ nhất tương ứng với cách tô màu sau (ở bên trái), cùng với một cách bố trí hướng mũi tên có thể có:

Ví dụ thứ hai đã được đề cập trong câu chuyện của bài toán như một trường hợp mà các điều kiện yêu cầu không thể đồng thời được thỏa mãn cho tất cả các ô.

Giới hạn

• $2 \le n \le 1000$.

Nhiệm vụ con

• Nhiệm vụ con 1 (10 điểm): $n=2$.
• Nhiệm vụ con 2 (25 điểm): Bảo đảm các ô đen tạo thành một miền liên thông, và ít nhất hai góc của mê cung là màu đen.
• Nhiệm vụ con 3 (25 điểm): Bảo đảm các ô trắng tạo thành một miền liên thông, và có ít hơn $4n-4$ ô đen.
• Nhiệm vụ con 4 (40 điểm): Không có giới hạn bổ sung.

Ghi chú

Một tập hợp các ô tạo thành một miền liên thông nếu giữa mỗi cặp ô của nó có một đường đi chỉ qua các ô thuộc tập hợp, di chuyển giữa các ô chung cạnh. Đặc biệt, các ô đen tạo thành một miền liên thông nếu giữa mỗi cặp ô đen có một đường đi chỉ gồm các ô đen. Tương tự, các ô trắng tạo thành một miền liên thông nếu giữa mỗi cặp ô trắng có một đường đi chỉ gồm các ô trắng.

Trong ví dụ thứ nhất, cả các ô trắng lẫn các ô đen đều tạo thành một miền liên thông.

Trong ví dụ thứ hai, các ô đen không tạo thành một miền liên thông vì bất kỳ đường đi nào giữa chúng cũng đi qua một ô trắng.