class Solution {
    /**
    IDEA:
    Before adding edge (u, v), check if there is already a path from u to v in the graph.
    If a path already exists → adding (u,v) creates a cycle → return that edge.
    Otherwise → add the edge and continue.  
    */
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;

        // Step-1 Create an adjacency list
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for(int i=0; i<=n; i++)
        {
            adj.add(new ArrayList<Integer>());
        }

        // Step-2 Connect edges in adjacency list
        for(int[] edge : edges)
        {
            int u = edge[0];
            int v = edge[1];

            boolean[] visited = new boolean[n+1];

            // Check if path already exists
            if(dfs(adj, visited, u, v))
            {
                return edge;
            }

            // Otherwise add edge
            adj.get(u).add(v);
            adj.get(v).add(u);
        }
        return new int[0];
    }

    public boolean dfs(ArrayList<ArrayList<Integer>> adj, boolean[] visited, int node, int targetNode)
    {
        if(node == targetNode)
            return true;

        visited[node] = true;

        for(int v : adj.get(node))
        {
            if(!visited[v])
            {
                if(dfs(adj, visited, v, targetNode))
                    return true;
            }
        }
        return false;
    }
}