题目描述

现在是 2121 年，你想配置一个 Neuralink 网络。

你有 $N$ 台服务器，每台服务器的 IP 地址用一个长度为 $M$ 的排列表示。排列中的元素为：

你希望网络规模尽可能大，但同时又担心安全问题：如果黑客知道了某个 IP 地址，那么他可能很容易找到一个与它相似的 IP 地址。

定义两个 IP 地址相似，当且仅当其中一个可以通过恰好一次交换操作变成另一个。一次交换操作指：选择排列中的两个不同位置，并交换这两个位置上的元素。

例如：

• $(0,1,2)$ 与 $(1,0,2)$ 相似，因为交换前两个位置即可；
• $(0,1,2)$ 与 $(1,2,0)$ 不相似，因为无法只通过一次交换得到。

你需要从 $N$ 台服务器中选出尽可能多的服务器，使得任意两台被选中的服务器，它们的 IP 地址都不相似。

请输出最多可以选择多少台服务器。

输入格式

第一行包含两个整数 $N,M$，表示服务器数量和每个 IP 地址排列的长度。

接下来 $N$ 行，每行包含 $M$ 个整数。第 $i$ 行表示第 $i$ 台服务器的 IP 地址，是一个 $0$ 到 $M-1$ 的排列。

输出格式

输出一个整数，表示最多可以选择多少台服务器，使得任意两台被选服务器的 IP 地址都不相似。

数据范围与约定

• $1\le N\le 2500$；
• $1\le M\le 5000$；
• 对任意 $1\le i\le N$，第 $i$ 个 IP 地址都是 $0$ 到 $M-1$ 的排列；
• 任意两个输入的 IP 地址互不相同。

子任务

样例 1

输入

3 3
0 1 2
2 1 0
1 0 2

输出

2

解释

可以选择 IP 地址 $(2,1,0)$ 和 $(1,0,2)$。

不能再选择 $(0,1,2)$，因为它与另外两个 IP 地址都相似。

样例 2

输入

5 5
0 1 2 3 4
1 0 2 3 4
0 1 2 4 3
0 4 2 3 1
4 1 2 3 0

输出

4

解释

可以选择除第一个 IP 地址外的所有 IP 地址。

样例 3

输入

6 3
0 1 2
0 2 1
1 0 2
1 2 0
2 1 0
2 0 1

输出

3

解释

可以选择 $(0,1,2)$、$(1,2,0)$、$(2,0,1)$。