题目描述

一幅地图由 $h$ 行 $w$ 列格子组成，每个格子都有一个表示颜色的正整数。两个共边且颜色相同的格子之间可以通行。所有能够通过这种方式互相到达的格子构成一个地块。

现在要在相邻两列之间设置一条隔离带。隔离带贯穿地图的上下边界，禁止跨越，但不会删除格子或改变格子的颜色。

你必须设置恰好一条隔离带。请确定它的位置，使隔离后整幅地图的地块总数最少，并求出这个最小值。

输入格式

第一行包含两个整数 $h,w$，表示地图的行数和列数。

接下来 $h$ 行，每行包含 $w$ 个整数，依次表示地图对应行中各个格子的颜色。

输出格式

输出一行一个整数，表示设置隔离带后，整幅地图最少有多少个地块。

样例输入 1

3 4
1 1 2 2
1 3 2 2
3 3 3 2

样例输出 1

4

样例 1 解释

在第 $2$、$3$ 列之间设置隔离带。左侧有颜色为 $1$、$3$ 的两个地块，右侧有颜色为 $2$、$3$ 的两个地块，共 $4$ 个；这是可以达到的最小值。

样例输入 2

2 3
1 2 1
1 2 1

样例输出 2

3

样例 2 解释

每一列各自构成一个地块。第 $1$、$3$ 列虽然颜色相同，但彼此不连通。两种隔离位置都使地图恰好有 $3$ 个地块。

数据范围与子任务

对于所有测试数据，保证$h\ge1,w\ge2,hw\le500000$，所有颜色均为 $1$ 至 $10^9$ 之间的整数。

每个子任务内的正式测试全部通过，才获得该子任务的分数。