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 1 1 3");
WillReturn.Add("2 2 1 3");
WillReturn.Add("2 1 1 3");
WillReturn.Add("2 2 2 2");
//4
}
else if (InputPattern == "Input2") {
WillReturn.Add("5 8");
WillReturn.Add("1 2 2 5 5 5 5 5");
WillReturn.Add("1 1 2 2 5 6 5 6");
WillReturn.Add("1 1 1 1 6 6 5 6");
WillReturn.Add("1 1 3 1 1 6 7 6");
WillReturn.Add("1 4 1 1 1 6 6 6");
//8
}
else if (InputPattern == "Input3") {
WillReturn.Add("1 6");
WillReturn.Add("1 1 2 2 3 3");
//3
}
else if (InputPattern == "Input4") {
WillReturn.Add("2 10");
WillReturn.Add("1 1 1 1 1 3 3 3 3 4");
WillReturn.Add("1 2 1 3 3 3 1 1 3 3");
//6
}
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);
// 左から右に累積UnionFind
var InsUnionFindWithAnyInfo1 = new UnionFindWithAnyInfo();
long[] RunSum1 = new long[UB_X + 1];
for (long X = 0; X <= UB_X; X++) {
for (long Y = 0; Y <= UB_Y; Y++) {
InsUnionFindWithAnyInfo1.MakeSet(GetHash(X, Y));
}
for (long Y = 0; Y <= UB_Y; Y++) {
// 下と接続
if (Y < UB_Y) {
ExecConn(X, Y, X, Y + 1, InsUnionFindWithAnyInfo1);
}
if (X > 0) {
// 左と接続
ExecConn(X, Y, X - 1, Y, InsUnionFindWithAnyInfo1);
}
}
RunSum1[X] = InsUnionFindWithAnyInfo1.TreeCnt;
}
// 右から左に累積UnionFind
var InsUnionFindWithAnyInfo2 = new UnionFindWithAnyInfo();
long[] RunSum2 = new long[UB_X + 1];
for (long X = UB_X; 0 <= X; X--) {
for (long Y = 0; Y <= UB_Y; Y++) {
InsUnionFindWithAnyInfo2.MakeSet(GetHash(X, Y));
}
for (long Y = 0; Y <= UB_Y; Y++) {
// 下と接続
if (Y < UB_Y) {
ExecConn(X, Y, X, Y + 1, InsUnionFindWithAnyInfo2);
}
if (X < UB_X) {
// 右と接続
ExecConn(X, Y, X + 1, Y, InsUnionFindWithAnyInfo2);
}
}
RunSum2[X] = InsUnionFindWithAnyInfo2.TreeCnt;
}
var AnswerList = new List<long>();
for (long X = 0; X <= UB_X; X++) {
if (X < UB_X) {
AnswerList.Add(RunSum1[X] + RunSum2[X + 1]);
}
}
Console.WriteLine(AnswerList.Min());
}
// 引数1 座標1のX
// 引数2 座標1のY
// 引数3 座標2のX
// 引数4 座標2のY
// 引数5 UnionFindのインスタンス
static void ExecConn(long pX1, long pY1, long pX2, long pY2,
UnionFindWithAnyInfo pInsUnionFindWithAnyInfo)
{
// 同じ値であること
if (mBanArr[pX1, pY1] != mBanArr[pX2, pY2]) {
return;
}
long Hash1 = GetHash(pX1, pY1);
long Hash2 = GetHash(pX2, pY2);
pInsUnionFindWithAnyInfo.Unite(Hash1, Hash2);
}
static long GetHash(long pX, long pY)
{
return pX * 1000000 + 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; // 木の枝の数
}
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)
{
mTreeCnt++;
NodeInfoDef WillAdd = new NodeInfoDef();
WillAdd.ParentNode = pNode;
WillAdd.Rank = 0;
WillAdd.Size = 1;
WillAdd.EdgeCnt = 0;
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;
}
else {
mNodeInfoDict[XNode].ParentNode = YNode;
mNodeInfoDict[YNode].Size += mNodeInfoDict[XNode].Size;
mNodeInfoDict[YNode].EdgeCnt++;
mNodeInfoDict[YNode].EdgeCnt += mNodeInfoDict[XNode].EdgeCnt;
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 void DebugPrint()
{
foreach (var EachPair in mNodeInfoDict.OrderBy(pX => pX.Key)) {
Console.WriteLine("mNodeInfoDict[{0}].ParentNode={1}",
EachPair.Key, EachPair.Value.ParentNode);
}
}
}