/* Please note that Edmond Algorithm or Blossom Algorithm implemented in this code for maximum matching in O(V*E) time is highly inspired from various papers , editorials and tutorials available from various websites. */ #include <iostream> #include <cstring> #include <vector> #include <cstdio> #include <queue> #include <algorithm> using namespace std; vector<int> adj[1005]; int Partner[1005], Parent[1005], Base[1005]; bool Used[1005], Bloss[1005]; int AugmentingPath(int , int); int FindHead(int , int); void TrackPath(int , int , int); bool IsPalindrom(string s) { int low=0; int high=s.size()-1; while(low<=high) { if(s[low]!=s[high]) { return false; } low++; high--; } return true; } void Solve(int n) { int GParent,GGParent; for (int i=0; i<n; i++) { if (Partner[i]==-1) { int v=AugmentingPath(i,n); while(v!=-1) { GParent=Parent[v]; GGParent=Partner[GParent]; Partner[v]=GParent; Partner[GParent]=v; v=GGParent; } } } return ; } string s[1005]; int main() { int t; while(cin>>t) { for (int i=0; i<=t; i++) { adj[i].clear(); Partner[i]=-1; } for(int i=0; i<t; i++) { cin>>s[i]; } for(int i=0; i<t; i++) { for(int j=i+1; j<t; j++) { string x=s[i]+s[j]; string y=s[j]+s[i]; if(IsPalindrom(x)==true || IsPalindrom(y)==true) { adj[i].push_back(j); adj[j].push_back(i); //printf("\nPushing %d %d\n",i,j); } } } Solve(t); /* printf("\nSo the respective partners are\n"); for (int i=0; i<t; i++) { printf("it is %d %d\n",i,Partner[i]); } */ int x,y; x=0; y=0; for(int i=0; i<t; i++) { if(Partner[i]==-1) { x++; } else { y++; } } printf("%d\n",x+y/2); }//end of test cases }//end of main int AugmentingPath(int root , int n) { for(int i=0; i<=1000; i++) { Used[i]=false; Parent[i]=-1; } for (int i=0; i<n; i++) { Base[i]=i; } queue<int> Q; Q.push(root); Used[root]=true; while(!(Q.empty())) { int v=Q.front(); Q.pop(); for (int i=0; i<adj[v].size(); i++) { int node=adj[v][i]; if (Base[v]==Base[node] || Partner[v]==node) { continue; } if (node==root || Partner[node]!=-1 && Parent[Partner[node]]!=-1) { int Temp=FindHead(v,node); memset(Bloss,0,sizeof(Bloss)); TrackPath(v,Temp,node); TrackPath(node,Temp,v); for(int i=0; i<n; ++i) { if (Bloss[Base[i]]) { Base[i]=Temp; if(Used[i]==false) { Used[i]=true; Q.push(i); } } } } else if(Parent[node]==-1) { Parent[node]=v; if(Partner[node]==-1) { return node; } node=Partner[node]; Used[node]=true; Q.push(node); } } } return -1; } int FindHead(int x , int y) { bool Track[1005]; for(int i=0; i<=1000; i++) { Track[i]=0; } while(1) { x=Base[x]; Track[x]=true; if (Partner[x]==-1) { break; } x=Parent[Partner[x]]; } while(1) { y=Base[y]; if(Track[y]==true) { return y; } y=Parent[Partner[y]]; } } void TrackPath(int x , int y , int z) { while (Base[x]!=y) { Bloss[Base[x]]=true; Bloss[Base[Partner[x]]]=true; Parent[x]=z; z=Partner[x]; x=Parent[Partner[x]]; } return ; }