Swap Free

#include <bits/stdc++.h>
using namespace std;

#define vi vector<int>
#define SZ(a) (int)a.size()
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

vector<int> AL[1005], graph[1005];
vi match, vis, cor;
int tempo;

void dfs(int v, int c) {
    cor[v] = c;
    for(int u : graph[v])
        if(!cor[u])
            dfs(u, 3 - c);
}

bool is_swap_free(string a, string b) {
    vector<int> p;
    for(int i = 0; i < SZ(a); ++i)
        if(a[i] != b[i])
            p.push_back(i);
    if(p.size() != 2) return true;
    swap(a[p[0]], a[p[1]]);
    return a == b ? false : true;
}

int Aug(int L) {
    if(vis[L] == tempo) return 0;
    vis[L] = tempo;
    for(int &R : AL[L]) {
        if((match[R] == -1) or Aug(match[R])) {
            match[R] = L;
            return 1;
        }
    }
    return 0;
}

int32_t main() {
   fastio;

   int n;
   cin >> n;

   vector<string> arr(n);
   for(string &w : arr) cin >> w;

   for(int i = 1; i <= n; ++i)
        for(int j = i + 1; j <= n; ++j)
            if(!is_swap_free(arr[i - 1], arr[j - 1])) {
                graph[i].push_back(j);
                graph[j].push_back(i);
            }

    cor.resize(n + 1, 0);

    for(int i = 1; i <= n; ++i)
        if(cor[i] == 0)
            dfs(i, 1);

    for(int i = 1; i <= n; ++i)
        for(int j : graph[i])
            if(cor[i] == 1 and cor[j] == 2)
                AL[i].push_back(j);

    vis.resize(n + 1, 0);
    match.resize(n + 1, -1);

    int match_cardinality = 0;

    for(int i = 1; i <= n; ++i)
        if(cor[i] == 1) {
            tempo++;
            match_cardinality += Aug(i);
        }
    cout << n - match_cardinality << '\n';

    return 0;
}