/**
1.1 "每一个节点只有一个父节点，除了根节点没有父节点"      -> 每个点的入度最大为一
1.2 "该树只有一个根节点，所有其他节点都是该根节点的后继"  -> 没有环
1.3 "一条附加的边"                                     -> 最多存在一个点的最大入度为2

2 所以根据两个合法条件可判断出3种异常情况
    2.1 不存在入度为2的点, 有环
    2.2 存在入度为2的点  , 没环
    2.3 存在入度为2的点  , 有环 , 此时删除任意一条边均可, 按题意删除靠后的

3.1 首先我们统计度数为2的点并记录对应的边, 最多2条, 按顺序记为c1 和 c2 (他们不一定存在)
3.2 然后开始用并查集判环:
    3.2.1 首先把c1, c2以外的边加入并查集, 如果出现环, 说明是 2.1 的情况, 返回当前边
    3.2.2 之后我们把c1 加入并查集      ,  如果出现环, 说明是 2.2 的情况, 返回c1
    3.2.3 否则                                     说明是 2.3 的情况, 返回c2
*/

class Solution {

    class UnionFindSet{
        int[] pre;
        public UnionFindSet(int n){
            pre = new int[n+1];
            for (int i = 0 ; i <= n; i++) pre[i] = i; 
        }

        public int find(int x){
            if (x != pre[x]) pre[x] = find(pre[x]);
            return pre[x];
        }

        public boolean union(int x , int y){
            int fx = find(x), fy = find(y);
            if (fx == fy) return false;
            pre[fx] = fy;
            return true;
        }
    }

    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n = edges.length;
        UnionFindSet ufs = new UnionFindSet(n);
        Map<Integer, Integer> ins = new HashMap<>();
        for (int i = 0; i < n; i++){
            int x = edges[i][0];
            int y = edges[i][1];
            if (ins.get(y) == null) ins.put(y, 0);
            if (ins.get(x) == null) ins.put(x, 0);
            ins.put(y, ins.get(y) + 1);
        }

        int[] candidate = new int[2];
        Arrays.fill(candidate, -1);
        for (int i = 0, j = 0; i < n; i++){
            int y = edges[i][1];
            if (ins.get(y) == 2) candidate[j++] = i;
        }

        for (int i = 0 ; i < n ; i ++){
            if (i == candidate[0] || i == candidate[1]) continue;
            int[] edge = edges[i];
            int x = edge[0];
            int y = edge[1];
            if (!ufs.union(x, y)) return edge;
        }

        int x = edges[candidate[0]][0];
        int y = edges[candidate[0]][1];
        if (ufs.union(x, y)) return edges[candidate[1]];
        return edges[candidate[0]];
    }
}