import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone {
	
	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 node, Node p, Node q) {
		
        Stack<Node> parentStack = new Stack<Node>();
        Stack<Integer> childIndexStack = new Stack<Integer>();
        Stack<Node> firstNodePath = null;
        while (!parentStack.empty() || node != null) {

        	if (node != null) {
        		
        		if (node == p || node == q) {

        			if (firstNodePath != null) {
        				parentStack.add(node);
        				int n = Math.min(parentStack.size(), firstNodePath.size());
        				for (int i = n - 1; i >= 0; i--) {
        					if (parentStack.get(i) == firstNodePath.get(i)) {
        						return parentStack.get(i); 
        					}
						}
       					return null;
        					
        			} else {
        				firstNodePath = new Stack<Node>();
        				firstNodePath.setSize(parentStack.size());
        				Collections.copy(firstNodePath, parentStack);
        				firstNodePath.push(node);
        			}

        		}
        		
        		if (!node.children.isEmpty()) {
        			parentStack.push(node);
        			childIndexStack.push(0);
        			node = node.children.get(0);
        		} else {
        			node = null;
        		}
        	    
        	} else {
        	
        		node = parentStack.peek();
        		Integer i = childIndexStack.pop() + 1;
        		if (i >= node.children.size()) {
        			node = null;
        			parentStack.pop();
        		} else {
        			node = node.children.get(i);
        			childIndexStack.push(i);
        		}
	            
	        }
        
        }
        return null;
        
	}


}