Đàn bò đã nghĩ ra một trò chơi mới đầy sáng tạo, nhưng thật bất ngờ lại đặt cho nó cái tên kém sáng tạo nhất có thể: “Moo”.

Trò Moo diễn ra trên một lưới gồm \(N \times N\) ô vuông. Một cô bò chiếm một ô bằng cách kêu “moo!” và viết số ID của mình vào ô đó.

Khi trò chơi kết thúc, mỗi ô đều chứa một số. Lúc này, một cô bò thắng nếu cô ấy đã tạo ra một vùng ô liên thông có kích thước ít nhất bằng mọi vùng khác. Một “vùng” được định nghĩa là một nhóm ô đều mang cùng một số ID, trong đó mỗi ô trong vùng kề trực tiếp với một ô khác trong cùng vùng ở phía trên, phía dưới, bên trái hoặc bên phải; các ô kề chéo không được tính.

Vì chơi riêng lẻ hơi nhàm chán, đàn bò cũng muốn ghép cặp để thi đấu theo đội. Một đội gồm hai cô bò có thể tạo ra một vùng như trên, nhưng giờ đây các ô trong vùng có thể thuộc về một trong hai cô bò của đội.

Với trạng thái cuối cùng của bàn chơi, hãy giúp đàn bò tính số ô trong vùng lớn nhất do một cô bò sở hữu, và số ô trong vùng lớn nhất mà một đội hai cô bò có thể tuyên bố sở hữu. Một vùng do đội hai cô bò tuyên bố sở hữu chỉ được tính nếu nó chứa số ID của cả hai cô bò trong đội, chứ không chỉ của một cô.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 250\)). Mỗi dòng trong \(N\) dòng tiếp theo chứa \(N\) số nguyên, mỗi số thuộc khoảng \(0 \ldots 10^6\), mô tả trạng thái cuối cùng của bàn chơi. Trên bàn bảo đảm có ít nhất hai số ID khác nhau.

Dữ liệu ra

Dòng đầu tiên in kích thước vùng lớn nhất do một cô bò sở hữu. Dòng thứ hai in kích thước vùng lớn nhất mà một đội hai cô bò có thể tuyên bố sở hữu.

Ví dụ

4
2 3 9 3
4 9 9 1
9 9 1 7
2 1 1 9

5
10

Nguồn

USACO 2018 US Open Contest, Silver — Multiplayer Moo

Tác giả bài toán: Brian Dean.