#include <iostream> #include <cstdint> #include <vector> #include <algorithm> using namespace std; int lca(vector<int>& match, vector<int>& base, vector<int>& p, int a, int b) { vector<bool> used(match.size(), false); while (true) { a = base[a]; used[a] = true; if (match[a] == -1) break; a = p[match[a]]; } while (true) { b = base[b]; if (used[b]) return b; b = p[match[b]]; } } void markPath(vector<int>& match, vector<int>& base, vector<bool>& blossom, vector<int>& p, int v, int b, int children) { for (; base[v] != b; v = p[match[v]]) { blossom[base[v]] = blossom[base[match[v]]] = true; p[v] = children; children = match[v]; } } int findPath(vector<vector<int> >& graph, vector<int>& match, vector<int>& p, int root) { int n = graph.size(); vector<bool> used(n, false); for (auto& i : p) i = -1; vector<int> base(n); for (int i = 0; i < n; ++i) base[i] = i; used[root] = true; int qh = 0; int qt = 0; vector<int> q(n); q[qt++] = root; while (qh < qt) { int v = q[qh++]; for (int to : graph[v]) { if (base[v] == base[to] || match[v] == to) continue; if (to == root || match[to] != -1 && p[match[to]] != -1) { int curbase = lca(match, base, p, v, to); vector<bool> blossom(n); markPath(match, base, blossom, p, v, curbase, to); markPath(match, base, blossom, p, to, curbase, v); for (int i = 0; i < n; ++i) if (blossom[base[i]]) { base[i] = curbase; if (!used[i]) { used[i] = true; q[qt++] = i; } } } else if (p[to] == -1) { p[to] = v; if (match[to] == -1) return to; to = match[to]; used[to] = true; q[qt++] = to; } } } return -1; } int maxMatching(vector<vector<int> >& graph) { int n = graph.size(); vector<int> match(n, -1); vector<int> p(n); for (int i = 0; i < n; ++i) { if (match[i] == -1) { int v = findPath(graph, match, p, i); while (v != -1) { int pv = p[v]; int ppv = match[pv]; match[v] = pv; match[pv] = v; v = ppv; } } } int matches = 0; for (int i = 0; i < n; ++i) if (match[i] != -1) ++matches; return matches / 2; } bool is_palindrome(string& s) { for (size_t i = 0; i < s.size() / 2; ++i) { if (s[i] != s[s.size() - 1 - i]) return false; } return true; } int main() { while (true) { size_t N = 0; char buff[1001]; cin.getline(buff, 1000, '\n'); if (buff[0] == '\0') { break; } N = atoi(buff); vector<string> blocks(N, ""); for (size_t i = 0; i < N; ++i) { char buff[1001]; cin.getline(buff, 1000, '\n'); blocks[i] = buff; } vector<vector<int> > graph(N); for (size_t i = 0; i < N; ++i) { for (size_t j = 0; j < N; ++j) { if (i != j) { string buff = blocks[i]; buff += blocks[j]; if (is_palindrome(buff)) { graph[i].push_back(j); graph[j].push_back(i); } } } } size_t max_matching = maxMatching(graph); cout << (N - 2 * max_matching) + max_matching << endl; } return 0; }