import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;

class LCA_fila {
	
	static class Node {
		List<Node> children = new ArrayList<Node>();
		Integer id;
		Node(Integer id) {
			this.id = id;
		}
		public String toString() {
			return id.toString();
		}
	}

	public static void main (String[] args) throws java.lang.Exception {
		
		//test data
		Node root = new Node(0);
		Node n1 = new Node(1);
		Node n2 = new Node(2);
		Node n3 = new Node(3);
		Node n1a = new Node(11);
		Node n1b = new Node(12);
		Node n3a = new Node(31);
		Node n3b = new Node(32);
		Node n3c = new Node(33);
		
		//connections
		root.children.add(n1);
		root.children.add(n2);
		root.children.add(n3);
		n1.children.add(n1a);
		n1.children.add(n1b);
		n3.children.add(n3a);
		n3.children.add(n3b);
		n3.children.add(n3c);
		
		//tests
		System.out.println("### Test 1 ###");
		Node r = findClosestCommonAncestor(root, n1b, n3a);
		System.out.println("Expected: " + root);
		System.out.println("Result: " + r);
		System.out.println("Passed --> " + (r == root));
		
		System.out.println("### Test 2 ###");
		r = findClosestCommonAncestor(root, n3, n3b);
		System.out.println("Expected: " + n3);
		System.out.println("Result: " + r);
		System.out.println("Passed --> " + (r == n3));
		
		System.out.println("### Test 3 ###");
		r = findClosestCommonAncestor(root, n3a, n3c);
		System.out.println("Expected: " + n3);
		System.out.println("Result: " + r);
		System.out.println("Passed --> " + (r == n3));
		
		System.out.println("### Test 4 ###");
		r = findClosestCommonAncestor(root, n2, n1a);
		System.out.println("Expected: " + root);
		System.out.println("Result: " + r);
		System.out.println("Passed --> " + (r == root));
		
	}
	

	static Node findClosestCommonAncestor(Node ancestralComum, Node p, Node q) {
		
		Queue<Node> fila = new ArrayBlockingQueue<Node>(100);
		
		while(true){
			
			// Adicionar todos os filhos do ancestral comum obtido ate agora na fila
			fila.clear();
			for( Node e: ancestralComum.children ){
				fila.add(e);
				fila.add(e);
			}
	
			// Vai passando os ancestrais ate descobrir os nodes e seus ancestrais
			Node p_ancestral=null, q_ancestral=null;
			while(p_ancestral == null || q_ancestral == null){
				Node e = fila.remove();
				Node a = fila.remove();

				for( Node filho : e.children ){
					fila.add(filho);
					fila.add(a);
				}

				if(e == p)
					p_ancestral = a;
				if(e == q)
					q_ancestral = a;	
			}
		
			// Condicoes para termino ou continuacao do algoritmo
			if(p_ancestral == q_ancestral)
				ancestralComum = p_ancestral;
			else
				break;
			if(p == ancestralComum || q == ancestralComum)
				break;
		}
			
		return ancestralComum;
	}

}