public int[] findRedundantDirectedConnection(int[][] edges) {

int N = edges.length;

int[] res1 = null;

int[] res2 = null;

int[] parent = new int[N+1];

boolean twoParentsExist = false;

for (int[] edge: edges) {

int u = edge[0];

int v = edge[1];

if (parent[v] != 0) {

res1 = new int[]{parent[v], v};

res2 = new int[]{u, v};

twoParentsExist = true;

break;

}

parent[v] = u;

}

DisjointSet djs = new DisjointSet(N);

for (int[] edge: edges) {

int u = edge[0];

int v = edge[1];

if (twoParentsExist && ((u == res1[0] && v == res1[1]) || (u == res2[0] && v == res2[1]))) continue;

int up = djs.find(u);

int vp = djs.find(v);

if (up == vp) {

return edge;

} else {

djs.union(u, v);

}

}

if (twoParentsExist && djs.find(res1[0]) == djs.find(res1[1])) {

return res1;

}

return res2;

}

class DisjointSet {

int[] parent;

int[] rank;

DisjointSet(int N) {

parent = new int[N+1];

for (int i=0; i<N; i++) parent[i] = i;

rank = new int[N+1];

}

int find(int x) {

if (parent[x] != x) {

parent[x] = find(parent[x]);

}

return parent[x];

}

void union(int x, int y) {

int xp = find(x);

int yp = find(y);

if (rank[xp] > rank[yp]) {

parent[yp] = xp;

} else if (rank[xp] < rank[yp]) {

parent[xp] = yp;

} else {

parent[xp] = yp;

rank[yp]++;

}

}

}

/**

public int[] findRedundantDirectedConnection2(int[][] edges) {

int[] can1 = {-1, -1};

int[] can2 = {-1, -1};

int[] parent = new int[edges.length + 1];

for (int i = 0; i < edges.length; i++) {

if (parent[edges[i][1]] == 0) {

parent[edges[i][1]] = edges[i][0];

} else {

can2 = new int[] {edges[i][0], edges[i][1]};

can1 = new int[] {parent[edges[i][1]], edges[i][1]};

edges[i][1] = 0;

}

}

for (int i = 0; i < edges.length; i++) {

parent[i] = i;

}

for (int i = 0; i < edges.length; i++) {

if (edges[i][1] == 0) {

continue;

}

int child = edges[i][1], father = edges[i][0];

if (root(parent, father) == child) {

if (can1[0] == -1) {

return edges[i];

}

return can1;

}

parent[child] = father;

}

return can2;

}

int root(int[] parent, int i) {

while (i != parent[i]) {

parent[i] = parent[parent[i]];

i = parent[i];

}

return i;

}