#include <iostream>#include <map>#include <string>#include <set>using namespace std;#define DBG#ifdef DBG #define PDBG(x); {cout<<x<<endl;}#else #define PDBG(x);#endiftypedef map<int, set<int> > AdjMat;set<int> Visited; // Contains all the nodes that have been visited so farmap<string, int> NodeIndex; // Maps each string to a unique integer, an IDAdjMat Graph; // Maps each NodeIndex to a set of nodes that are connected to itint NodeLen, // The no. of nodes in the Graph root, // The Root of the current DFS steps, // The length of the path taken so far maxVal; // The max length Cycle so far/* Pre : Parent is a node in a graph that has an edge leading to child * Parent is a node in the visited set * Post : Returns true if and only if - * There is no loop between child and parent * parent is the only node in Visited that loves child * child doesn't love any one in the Visited set */inline bool isTrueLove (int child, int parent){ set<int>::iterator iter; if(Graph[child].find(parent) != Graph[child].end()) { // This means that the parent loves the child and the child loves the parent! PDBG("Child :"<<child<<" loves parent at "<<parent); return false; } //Make Sure that child is only loved by the parent in all the memebers of Visited for(iter = Visited.begin(); iter != Visited.end(); iter++) { if( (*iter != parent) && (Graph[*iter].find(child) != Graph[*iter].end())) { PDBG("State :"<<child<<" has a lover at "<<*iter); return false; } } //Make Sure that child does NOT love any member of Visited except the root for(iter = Graph[child].begin(); child!= root && iter != Graph[child].end(); iter++) { if( (*iter != root) && (Visited.find(*iter) != Visited.end())) { PDBG("child :"<<child<<" loves visitor at "<<*iter); return false; } } return true;}void findMaxCycle (int parent){ set<int>::iterator child; PDBG("parent :"<<parent); Visited.insert(parent); for(child = Graph[parent].begin(); child != Graph[parent].end(); child++) { if ((Visited.find(*child) == Visited.end()) ) { if(isTrueLove(*child, parent)) { PDBG("From :"<<parent<<" To :"<<*child); steps++; findMaxCycle(*child); steps--; } } // I think i have to handle some edge case here. Yet to find it out //------------------------------------------------------------- // if the child is already visited and is the root, then we have completed the cycle. else if ((*child == root ) && (maxVal < steps+1) ) { maxVal = steps+1; PDBG("Value set :"<<maxVal); } } Visited.erase(parent);}int main(){ int n; string lhs, rhs; cin>>n; // Numbering of nodes starts from 1 //as operator [] return default value(which is 0 for int) when the key is not present NodeLen = 1; for(int i=0; i<n; i++) { int li, ri; cin>>lhs>>rhs; if( (li = NodeIndex[lhs]) == 0) li = NodeIndex[lhs] = NodeLen++; if( (ri = NodeIndex[rhs]) == 0) ri = NodeIndex[rhs] = NodeLen++; Graph[li].insert(ri); }#ifdef DBG map<string, int>::iterator iter; for(int i=1; i<NodeLen; i++) { cout<<i<<" :"<<endl; for(set<int>::iterator iter = Graph[i].begin(); iter != Graph[i].end(); iter++) cout<<*iter<<" "; cout<<endl; }#endif maxVal = -1; for(int i=1; i<NodeLen; i++) { root = i; steps = 0; PDBG(" Root :"<<root); findMaxCycle(i); } if(maxVal>2) cout<<maxVal<<endl; else cout<<0<<endl; return 0;}