using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("4 4");
WillReturn.Add("1 2 3 1");
WillReturn.Add("2 2 3 1");
WillReturn.Add("1 2 3 1");
WillReturn.Add("3 3 2 2");
//9
}
else if (InputPattern == "Input2") {
WillReturn.Add("2 10");
WillReturn.Add("1 2 2 1 3 3 3 3 1 1");
WillReturn.Add("1 1 1 1 1 1 1 3 3 3");
//18
}
else if (InputPattern == "Input3") {
WillReturn.Add("5 5");
WillReturn.Add("1 1 1 1 1");
WillReturn.Add("1 1 1 1 1");
WillReturn.Add("1 1 1 1 1");
WillReturn.Add("1 1 1 1 1");
WillReturn.Add("1 1 1 1 1");
//25
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static long[] GetSplitArr(string pStr)
{
return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
}
static long[,] mBanArr;
static long UB_X;
static long UB_Y;
static void Main()
{
List<string> InputList = GetInputList();
mBanArr = CreateBanArr(InputList.Skip(1));
UB_X = mBanArr.GetUpperBound(0);
UB_Y = mBanArr.GetUpperBound(1);
var InsUnionFindWithAnyInfo = new UnionFindWithAnyInfo();
// UnionFindのノードを作成
for (long Y = 0; Y <= UB_Y; Y++) {
for (long X = 0; X <= UB_X; X++) {
long CurrHash = GetHash(X, Y);
InsUnionFindWithAnyInfo.MakeSet(CurrHash, mBanArr[X, Y]);
}
}
// 4近傍と接続
for (long Y = 0; Y <= UB_Y; Y++) {
for (long X = 0; X <= UB_X; X++) {
Action<long, long> ConnAct = (pTargetX, pTargetY) =>
{
if (pTargetX < 0 || UB_X < pTargetX) return;
if (pTargetY < 0 || UB_Y < pTargetY) return;
long BaseColor = mBanArr[X, Y];
if (mBanArr[pTargetX, pTargetY] != BaseColor) return;
long BaseHash = GetHash(X, Y);
long TargetHash = GetHash(pTargetX, pTargetY);
InsUnionFindWithAnyInfo.Unite(BaseHash, TargetHash);
};
ConnAct(X, Y - 1);
ConnAct(X, Y + 1);
ConnAct(X - 1, Y);
ConnAct(X + 1, Y);
}
}
var RootNodeSet = new HashSet<long>();
for (long Y = 0; Y <= UB_Y; Y++) {
for (long X = 0; X <= UB_X; X++) {
long BaseHash = GetHash(X, Y);
long RootNode = InsUnionFindWithAnyInfo.FindSet(BaseHash);
RootNodeSet.Add(RootNode);
}
}
// 解候補を列挙
var AnswerList = new List<long>();
foreach (long EachRootNode in RootNodeSet) {
HashSet<long> ShimaNodeSet = InsUnionFindWithAnyInfo.GetNodeSet(EachRootNode);
// 隣接ノードの代表ノードのSet
HashSet<long> RinsetuRootNodeSet = new HashSet<long>();
Action<long, long> AddAct = (pTargetX, pTargetY) =>
{
if (pTargetX < 0 || UB_X < pTargetX) return;
if (pTargetY < 0 || UB_Y < pTargetY) return;
long BaseCoor = InsUnionFindWithAnyInfo.GetColor(EachRootNode);
if (mBanArr[pTargetX, pTargetY] == BaseCoor) return;
long CurrHash = GetHash(pTargetX, pTargetY);
long CurrRoot = InsUnionFindWithAnyInfo.FindSet(CurrHash);
RinsetuRootNodeSet.Add(CurrRoot);
};
foreach (long EachShimaNode in ShimaNodeSet) {
long CurrX = EachShimaNode / 1000;
long CurrY = EachShimaNode % 1000;
AddAct(CurrX, CurrY - 1);
AddAct(CurrX, CurrY + 1);
AddAct(CurrX - 1, CurrY);
AddAct(CurrX + 1, CurrY);
}
// マス合計[色]なDict
var CntDict = new Dictionary<long, long>();
foreach (long EachRinsetuRootNode in RinsetuRootNodeSet) {
long CurrColor = InsUnionFindWithAnyInfo.GetColor(EachRinsetuRootNode);
HashSet<long> CurrNodeSet = InsUnionFindWithAnyInfo.GetNodeSet(EachRinsetuRootNode);
if (CntDict.ContainsKey(CurrColor) == false) {
CntDict[CurrColor] = 0;
}
CntDict[CurrColor] += CurrNodeSet.Count;
}
AnswerList.Add(ShimaNodeSet.Count);
foreach (var EachPair in CntDict) {
AnswerList.Add(ShimaNodeSet.Count + EachPair.Value);
}
}
Console.WriteLine(AnswerList.Max());
}
static long GetHash(long pX, long pY)
{
return pX * 1000 + pY;
}
////////////////////////////////////////////////////////////////
// IEnumerable<string>をlongの2次元配列に設定
////////////////////////////////////////////////////////////////
static long[,] CreateBanArr(IEnumerable<string> pStrEnum)
{
var StrList = new List<string>(pStrEnum);
if (StrList.Count == 0) {
return new long[0, 0];
}
long[] LongArr = { };
Action<string> SplitAct = pStr =>
LongArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
SplitAct(StrList[0]);
long UB_X = LongArr.GetUpperBound(0);
long UB_Y = StrList.Count - 1;
long[,] WillReturn = new long[UB_X + 1, UB_Y + 1];
for (long Y = 0; Y <= UB_Y; Y++) {
SplitAct(StrList[(int)Y]);
for (long X = 0; X <= UB_X; X++) {
WillReturn[X, Y] = LongArr[X];
}
}
return WillReturn;
}
}
// UnionFindWithAnyInfoクラス
internal class UnionFindWithAnyInfo
{
private class NodeInfoDef
{
internal long ParentNode;
internal long Rank;
internal long Size; // 木のノード数
internal long EdgeCnt; // 木の枝の数
internal long Color; // 色
internal HashSet<long> NodeSet;
}
private Dictionary<long, NodeInfoDef> mNodeInfoDict =
new Dictionary<long, NodeInfoDef>();
// 森にある木の数
private long mTreeCnt = 0;
// 森にある木の数を返す
internal long TreeCnt
{
get { return mTreeCnt; }
}
// 要素が1つである木を森に追加
internal void MakeSet(long pNode, long pColor)
{
mTreeCnt++;
NodeInfoDef WillAdd = new NodeInfoDef();
WillAdd.ParentNode = pNode;
WillAdd.Rank = 0;
WillAdd.Size = 1;
WillAdd.EdgeCnt = 0;
WillAdd.Color = pColor;
WillAdd.NodeSet = new HashSet<long>() { pNode };
mNodeInfoDict[pNode] = WillAdd;
}
// 合併処理
internal void Unite(long pX, long pY)
{
long XNode = FindSet(pX);
long YNode = FindSet(pY);
// 既に同じ木の場合
if (XNode == YNode) {
mNodeInfoDict[XNode].EdgeCnt++;
return;
}
mTreeCnt--;
long XRank = mNodeInfoDict[XNode].Rank;
long YRank = mNodeInfoDict[YNode].Rank;
if (XRank > YRank) {
mNodeInfoDict[YNode].ParentNode = XNode;
mNodeInfoDict[XNode].Size += mNodeInfoDict[YNode].Size;
mNodeInfoDict[XNode].EdgeCnt++;
mNodeInfoDict[XNode].EdgeCnt += mNodeInfoDict[YNode].EdgeCnt;
mNodeInfoDict[XNode].NodeSet.UnionWith(mNodeInfoDict[YNode].NodeSet);
}
else {
mNodeInfoDict[XNode].ParentNode = YNode;
mNodeInfoDict[YNode].Size += mNodeInfoDict[XNode].Size;
mNodeInfoDict[YNode].EdgeCnt++;
mNodeInfoDict[YNode].EdgeCnt += mNodeInfoDict[XNode].EdgeCnt;
mNodeInfoDict[YNode].NodeSet.UnionWith(mNodeInfoDict[XNode].NodeSet);
if (XRank == YRank) {
mNodeInfoDict[YNode].Rank++;
}
}
}
// ノードを引数として、木の根を取得
internal long FindSet(long pTargetNode)
{
// 根までの経路上のノードのList
var PathNodeList = new List<long>();
long CurrNode = pTargetNode;
while (CurrNode != mNodeInfoDict[CurrNode].ParentNode) {
PathNodeList.Add(CurrNode);
CurrNode = mNodeInfoDict[CurrNode].ParentNode;
}
// 経路圧縮 (親ポインタの付け替え)
foreach (long EachPathNode in PathNodeList) {
mNodeInfoDict[EachPathNode].ParentNode = CurrNode;
}
return CurrNode;
}
// ノードを引数として、木のサイズを取得
internal long GetSize(long pNode)
{
long RootNode = FindSet(pNode);
return mNodeInfoDict[RootNode].Size;
}
// ノードを引数として、木の枝数を取得
internal long GetEdgeCnt(long pNode)
{
long RootNode = FindSet(pNode);
return mNodeInfoDict[RootNode].EdgeCnt;
}
// ノードを引数として、色を取得
internal long GetColor(long pNode)
{
long RootNode = FindSet(pNode);
return mNodeInfoDict[RootNode].Color;
}
// ノードを引数として、NodeSetを取得
internal HashSet<long> GetNodeSet(long pNode)
{
long RootNode = FindSet(pNode);
return mNodeInfoDict[RootNode].NodeSet;
}
internal void DebugPrint()
{
foreach (var EachPair in mNodeInfoDict.OrderBy(pX => pX.Key)) {
Console.WriteLine("mNodeInfoDict[{0}].ParentNode={1}",
EachPair.Key, EachPair.Value.ParentNode);
}
}
}