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

class Ideone {
	
	static class Node {
		Node parent;
		Integer id;
		Node(Integer id, Node parent) {
			this.id = id;
			this.parent = parent;
		}
		public String toString() {
			return id.toString();
		}
	}
	
	public static void main (String[] args) throws java.lang.Exception {
		
		//test data
		Node root = new Node(0, null);
		Node n1 = new Node(1, root);
		Node n2 = new Node(2, root);
		Node n3 = new Node(3, root);
		Node n1a = new Node(11, n1);
		Node n1b = new Node(12, n1);
		Node n3a = new Node(31, n3);
		Node n3b = new Node(32, n3);
		Node n3c = new Node(33, n3);
		
		//tests
		System.out.println("### Test 1 ###");
		Node r = findClosestCommonAncestor(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(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(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(n2, n1a);
		System.out.println("Expected: " + root);
		System.out.println("Result: " + r);
		System.out.println("Passed --> " + (r == root));
		
	}
	
	static Node findClosestCommonAncestor(Node p, Node q) {
		if (p == null || q == null) return null;
		
		//guarda os pais do nó P, incluindo o próprio
        Set<Node> parentsOfP = new HashSet<Node>();
        while (p != null) {
        	parentsOfP.add(p);
        	p = p.parent;
        }
        
		//procura o primeiro pai de Q que está entre os pais de P
        while (q != null) {
        	if (parentsOfP.contains(q)) {
        		return q;
        	}
        	q = q.parent;
        }
        return null;// not in the same tree
   	}


}