/**
 * Created by 1000132937 on 3/24/2018.
 */
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.HashMap;
import java.util.Set;
import java.util.HashSet;
import java.util.Queue;
import java.util.LinkedList;

public class GitVersion {
    static class GitNode {
        int val;
        List<GitNode> neighbors;
        List<GitNode> parents;
        public GitNode(int val) {
            this.val = val;
            this.neighbors = new ArrayList<GitNode>();
            this.parents = new ArrayList<GitNode>();
        }
    }

    public static void main(String[] args) {
        GitVersion gv = new GitVersion();
        int[][] commits = new int[][] {{0, 1}, {1, 3}, {3, 5}, {0, 2}, {2, 4},{4, 5}};
        // construct the graph
        Map<Integer, GitNode> map = new HashMap<Integer, GitNode>();
        for (int[] commit: commits) {
            int from = commit[0];
            int to = commit[1];

            GitNode fromNode = null;
            GitNode toNode = null;
            if (map.containsKey(from)) {
                fromNode = map.get(from);
            } else {
                fromNode = new GitNode(from);
                map.put(from, fromNode);
            }

            if (map.containsKey(to)) {
                toNode = map.get(to);

            } else {
                toNode = new GitNode(to);
                map.put(to, toNode);
            }

            fromNode.neighbors.add(toNode);
            toNode.parents.add(fromNode);
        }

        // find the root node
        GitNode root = null;
        Map<GitNode, Integer> inDegree = new HashMap<GitNode, Integer>();
        for (GitNode node : map.values()) {
            if (!inDegree.containsKey(node)) {
                inDegree.put(node, 0);
            }
            for(GitNode nei : node.neighbors) {
                if(inDegree.containsKey(nei)) {
                    inDegree.put(nei, inDegree.get(nei) + 1);
                } else {
                    inDegree.put(nei, 1);
                }
            }
        }

        for (GitNode node : inDegree.keySet()) {
            if(inDegree.get(node) == 0) {
                root = node;
                break;
            }
        }

        GitNode node1 = map.get(3);
        GitNode node2 = map.get(4);

        List<Integer> result = gv.findCommits(root);
        int lca = gv.findLCA(node1, node2);
    }


    public List<Integer> findCommits(GitNode root){
        List<Integer> result = new ArrayList<Integer>();
        Set<GitNode> visited = new HashSet<GitNode>();
        Queue<GitNode> queue = new LinkedList<GitNode>();
        findCommitsHelper(root, visited, queue, result);
        return result;
    }

    private void findCommitsHelper(GitNode root, Set<GitNode> visited, Queue<GitNode> queue, List<Integer> result) {
        if (root == null) {
            return;
        }
        queue.offer(root);
        while(!queue.isEmpty()) {
            GitNode cur = queue.poll();
            if(!visited.contains(cur)) {
                visited.add(cur);
                result.add(cur.val);

                for(GitNode nei : cur.neighbors) {
                    queue.offer(nei);
                }
            }
        }
    }

    private void dfs(GitNode root, List<Integer> result) {
        if (root == null) {
            return;
        }

        Set<GitNode> visited = new HashSet<GitNode>();
        Queue<GitNode> queue = new LinkedList<GitNode>();

        queue.offer(root);
        while(!queue.isEmpty()) {
            GitNode cur = queue.poll();
            if (!visited.contains(cur)) {
                result.add(cur.val);
                visited.add(cur);
                for(GitNode parent : cur.parents){
                    queue.offer(parent);
                }
            }
        }
    }
    public int findLCA(GitNode node1, GitNode node2) {
        if (node1 == null || node2 == null) {
            throw new NullPointerException();
        }
        List<Integer> result1 = new ArrayList<Integer>();
        dfs(node1, result1);
        List<Integer> result2 = new ArrayList<Integer>();
        dfs(node2, result2);
        int i = result1.size() - 1;
        int j = result2.size() - 1;

        for (; i >= 0 && j >= 0; i--, j--) {
            if (result1.get(i) == result2.get(j)){
                continue;
            } else {
                break;
            }
        }
        return result1.get(i + 1);
    }
}