// tested by Hightail: https://github.com/dj3500/hightail #include <iostream> #include <cstdio> #include <string> #include <vector> #include <set> #include <map> #include <queue> #include <cmath> #include <algorithm> #include <sstream> #include <stack> #include <cstring> #include <iomanip> #include <ctime> #include <cassert> using namespace std; #define pb push_back #define INF 1001001001 #define FOR(i,n) for(int (i)=0;(i)<(n);++(i)) #define FORI(i,n) for(int (i)=1;(i)<=(n);++(i)) #define mp make_pair #define pii pair<int,int> #define ll long long #define vi vector<int> #define SZ(x) ((int)((x).size())) #define fi first #define se second #define wez(n) int (n); scanf("%d",&(n)); #define wez2(n,m) int (n),(m); scanf("%d %d",&(n),&(m)); #define wez3(n,m,k) int (n),(m),(k); scanf("%d %d %d",&(n),&(m),&(k)); inline void pisz(int n) { printf("%d\n",n); } template<typename T,typename TT> ostream& operator<<(ostream &s,pair<T,TT> t) {return s<<"("<<t.first<<","<<t.second<<")";} template<typename T> ostream& operator<<(ostream &s,vector<T> t){FOR(i,SZ(t))s<<t[i]<<" ";return s; } #define DBG(vari) cerr<<"["<<__LINE__<<"] "<<#vari<<" = "<<(vari)<<endl; #define ALL(t) t.begin(),t.end() #define FOREACH(i,t) for (__typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define TESTS wez(testow)while(testow--) #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i) #define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i) #define REMAX(a,b) (a)=max((a),(b)); #define REMIN(a,b) (a)=min((a),(b)); #define IOS ios_base::sync_with_stdio(0); #define N 1111 int n; // IN: liczba wierzcholkow bool edge[N][N]; // IN: macierz sasiedztwa (mozna zmienic na liste) int mate[N]; // OUT: wierzcholek skojarzony (-1 oznacza brak) int label[N], base[N], prev1[N], prev2[N]; bool mark[N]; bool prepare (int v) { while(1) { mark[v] = !mark[v]; if (mate[v] == -1) return mark[v]; v = base[prev2[mate[v]]]; } } int shrink (int v, int b1, int b2, queue<int> &Q) { while (mark[v]) { prev1[v] = b1; prev2[v] = b2; mark[mate[v]] = 1; Q.push(mate[v]); v = base[prev2[mate[v]]]; } return v; } bool make_blos (int i, int j, int bi, int bj, queue<int> &Q) { if (label[i]!=1 || i==j) return 0; if (prepare(i), prepare(j)) return 1; int b = (shrink(i, bi, bj, Q), shrink(j, bj, bi, Q)); FOR(v,n) if (mark[base[v]]) base[v] = b; return 0; } void rematch(int i, int j) { int next = mate[i]; mate[i] = j; if (next==-1) return; mate[next] = -1; rematch(prev2[next], prev1[next]); rematch(prev1[next], prev2[next]); } bool augment() { queue<int> Q; FOR(i,n) { label[i] = mate[i]==-1; if (mate[i]==-1) Q.push(i); mark[i] = 0; base[i] = i; } while (!Q.empty()) { int cur = Q.front(); Q.pop(); FOR(i,n) /*tu zmienic*/ if (edge[cur][i] && i!=mate[cur]) { if (!label[i]) { label[i] = -1; label[mate[i]] = 1; Q.push(mate[i]); prev1[i] = i; prev2[i] = cur; } else if (make_blos(base[i], base[cur], i, cur, Q)) { rematch(i, cur); rematch(cur, i); return 1; } } } return 0; } int compute_gcm() { // zwraca licznosc maksymalnego skojarzenia fill_n(mate, n, -1); int res = 0; while (augment()) ++res; return res; } string s[N]; char buf[2111]; int main () { while (1 == scanf("%d", &n)) { FOR(i,n) { scanf("%s", buf); s[i] = buf; } FOR(i,n) FOR(j,n) edge[i][j] = 0; FOR(i,n) FOR(j,n) if (i != j) { // jesli ok, to zamarkuj oba //FOR(k,SZ(s[i])) buf[k] = s[i][k]; //FOR(k,SZ(s[j])) buf[k+SZ(s[i])] = s[j][k]; bool wrong = 0; for (int a = 0, b = SZ(s[i]) + SZ(s[j]) - 1; a < b; ++a, --b) { char c = (a < SZ(s[i])) ? s[i][a] : s[j][a - SZ(s[i])]; char d = (b < SZ(s[i])) ? s[i][b] : s[j][b - SZ(s[i])]; if (c != d) { wrong = 1; break; } } if (!wrong) { edge[i][j] = edge[j][i] = 1; } } pisz(n - compute_gcm()); } }