import java.util.*;

public class LongestPathMatchedCardsHierholzer {
	static class Card {
		String suite;
		String figure;
		
		//Constructor, Time O(1) Space O(1)
	    Card (String s, String f) { 
	        suite = s; 
	        figure = f;
	    } 

	    //either suite or figure are the same to match
	    //Time O(1), Space O(1)
	    public boolean matched(Object o) {
			if (o instanceof Card) {
				Card s = (Card) o;
				return  this.suite == s.suite || this.figure == s.figure;
			} else {
				return false;
	    	}
	    } 
	    
	    //Time O(1), Space O(1)
	    @Override
	    public String toString() {
	    	return "("+ suite+", "+ figure +")";
	    }
	}
	
	//Use Hierholzer's algorithms, Time O(V*E), Space O(E+V) 
	//E number is of edges, V is number of vertices
	public static int longestChains(List<Card> input) {
		Map<Card, LinkedList<Card>> adj = buildGraph(input);	
	    Map<Card,Integer> degrees = new LinkedHashMap<>();	  
	    for (Card key: adj.keySet()) { //number of degrees are the number of out edges
	        degrees.put(key,adj.get(key).size());
	    }
	    TreeMap<Integer, List<Set<Card>>> links = new TreeMap<>(Collections.reverseOrder()); //track all linked chains, keys are theirs sizes
	    List<Card> allKeys = new ArrayList<>(adj.keySet()); //all nodes will be checked as start node
	    for (int i = 0 ;i < allKeys.size(); i++) {
	    	Stack<Card> stack = new Stack<>(); //keep track visited nodes
		    Set<Card> chain = new LinkedHashSet<>(); //keep track the linked cards(not necessary in order)
		    Card first = allKeys.get(i); //choose one in adjacency list keys
		    stack.push(first); //start node
		    Card curr = first; 	  
		    while (!stack.empty()) { //run out cards
		        if (degrees.get(curr) > 0) { //pick next unvisited edge 
		            stack.push(curr); //push to stack  
		            Card next = adj.get(curr).getLast();
		            degrees.put(curr, degrees.get(curr) - 1); //degree decrease
		            adj.get(curr).removeLast();
		            curr = next;; //next one to visit
		        } else  { //backtracking when next is not linkable
		        	chain.add(curr); //add to chain
			        curr = stack.peek(); //next to visit
			        stack.pop();
		        }
		    }
		    int len = chain.size(); //save the chain size and chains in links, size is the key
		    links.putIfAbsent(len, new LinkedList<>());
		    links.get(len).add(chain);
	    }
	    return links.firstKey(); //return the largest one
	}
	
	//Build undirected graph adjacency list from input, Time O(V^2), Space O(E+V)  
	private static Map<Card, LinkedList<Card>> buildGraph(List<Card> input) {
		Map<Card, LinkedList<Card>> adj = new LinkedHashMap<>();
		int n = input.size();
		for (int i = 0; i < n-1; i++) {
			Card card1 = input.get(i);  //get one node
			adj.putIfAbsent(card1, new LinkedList<>()); //save node to adjacency list
			for (int j = i+1; j < n; j++) { 
				Card card2 = input.get(j);	//get another node 			
				adj.putIfAbsent(card2, new LinkedList<>()); //save node to adjacency list
				if (card1.matched(card2)) {					
					adj.get(card1).add(card2); //add edges	
					adj.get(card2).add(card1); //add edges	
				}
			}
		}	
		return adj;
	}
	
	public static void main(String[] args) {	
		//case1
		String[][] input = {{"H","3"},{"H","4"},{"S","4"},{"D","1"}, {"D", "5"}}; 	
		//create nodes 
		List<Card> nodes = new ArrayList<>();
		int n = input.length;
		for (int i = 0; i < n; i++) {
			nodes.add(new Card( input[i][0], input[i][1]));
		}	
		System.out.println("Case1 max number of cards: "+ longestChains(nodes));
		
		//case2
		String[][] input1 = {{"H","3"},{"H","4"},{"S","4"},{"D","1"}, {"D", "5"}, {"H", "1"}};
		List<Card> nodes1 = new ArrayList<>();
		int n1 = input1.length;
		for (int i = 0; i < n1; i++) {
			nodes1.add(new Card( input1[i][0], input1[i][1]));
		}	
		System.out.println("Case2 max number of cards: "+ longestChains(nodes1));
	}
}