// Runtime: 2 ms
// Your runtime beats 30.41 % of java submissions.
class Solution {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n = edges.length;

        int[] in = new int[n+1];
        Arrays.fill(in, -1);

        List<Integer>[] adj = new List[n+1];
        for (int node = 1; node <= n; node++) adj[node] = new LinkedList<Integer>();
        for (int edgeNo = 0; edgeNo < n; edgeNo++) adj[edges[edgeNo][0]].add(edgeNo);

        int[] drains = null;
        for (int edgeNo = 0; edgeNo < n; edgeNo++) {
            int to = edges[edgeNo][1];
            if (in[to] != -1) {
                drains = new int[] { in[to], edgeNo };
            }
            in[to] = edgeNo;
        }

        if (drains != null) {
            int source = -1;
            for (int node = 1; node <= n; node++){
                if (in[node] == -1){
                    source = node;
                    break;
                }
            }

            int first = Math.min(drains[0], drains[1]);
            int last = Math.max(drains[0], drains[1]);

            if (reachable(source, edges[last][1], last, adj, edges))
                return edges[last];
            else return edges[first];
        }

        boolean[] visited = new boolean[n+1];
        for (int node = 1; node <= n; node++)
            if (!visited[node]) {
                int res = dfs(node, visited, adj, edges);
                if (res != -1) return edges[res];
            }
        return null;
    }

    private int dfs(int node, boolean[] visited, List<Integer>[] adj, int[][] edges) {
        visited[node] = true;

        for (int edgeNo: adj[node]) {
            int[] edge = edges[edgeNo];
            int next = edge[1];

            if (visited[next]) return edgeNo;

            int res = dfs(next, visited, adj, edges);
            if (res != -1) return Math.max(res, edgeNo);
        }

        return -1;
    }

    private boolean reachable(int node, int target, int exclEdge, List<Integer>[] adj, int[][] edges) {
        if (node == target) return true;

        for (int edgeNo: adj[node]) {
            if (edgeNo == exclEdge) continue;
            int[] edge = edges[edgeNo];
            int next = edge[1];

            if (reachable(next, target, exclEdge, adj, edges)) return true;
        }

        return false;
    }
}