#include using namespace std; struct UnionFind { // The range of node number is u 0 v n-1 vector rank, parents; UnionFind() {} UnionFind(int n) { // make n trees. rank.resize(n, 0); parents.resize(n, 0); for (int i = 0; i < n; i++) { makeTree(i); } } void makeTree(int x) { parents[x] = x; // the parent of x is x rank[x] = 0; } bool isSame(int x, int y) { return findRoot(x) == findRoot(y); } void unite(int x, int y) { x = findRoot(x); y = findRoot(y); if (rank[x] > rank[y]) { parents[y] = x; } else { parents[x] = y; if (rank[x] == rank[y]) { rank[y]++; } } } int findRoot(int x) { if (x != parents[x]) parents[x] = findRoot(parents[x]); return parents[x]; } }; struct Edge { long long u; long long v; long long cost; }; bool comp_e(const Edge &e1, const Edge &e2) { return e1.cost < e2.cost; } struct Kruskal { UnionFind uft; long long sum; vector edges; int V; Kruskal(const vector &edges_, int V_) : edges(edges_), V(V_) { init(); } void init() { sort(edges.begin(), edges.end(), comp_e); uft = UnionFind(V); sum = 0; for (auto e : edges) { if (!uft.isSame(e.u, e.v)) { uft.unite(e.u, e.v); sum += e.cost; } } } }; int main() { int N, L; cin >> N >> L; int E=(N * N) / 2; vector vec(N); for (int i = 0; i < N; i++) { cin >> vec[i]; } vector edges(E); int count = 0; for (int i = 0; i < N-1; i++) { for (int j = i + 1; j < N; j++) { int sum = 0; for (int k = 0; k < L; k++) { if(vec[i][k] != vec[j][k]) { sum++; } } Edge e = {i, j, sum}; edges[count] = e; count++; } } Kruskal krs(edges, N); cout << krs.sum << endl; return 0; }