class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int N = edges.size()+1;
        vector<vector<int>> grid(N,vector<int>(N,0));
        vector<vector<int>> cycle(N,vector<int>(N,0));
        vector<int> vis(N,0);
        for(auto edge:edges) {
            grid[edge[0]][edge[1]]=1;
            grid[edge[1]][edge[0]]=1;
        }


        queue<pair<int,int>> q;
        for(int i=1;i<N;i++) {
            if(vis[i]==0) {
                q.push({i,-1});
              vis[i]=1;
                while(!q.empty()) {

                    pair<int,int> current = q.front();

                    int c = current.first;
                    int p = current.second;
                    q.pop();
                    for(int x=1;x<N;x++) {
                        if(grid[c][x]==1 ) {
                            if(vis[x]==0) {
                                q.push({x,c});
                                vis[x]=1;

                            } else if(vis[x]==1 && p!=x ) {
                                //cyclic edge. add it
                                cycle[x][c]=1;
                                cycle[c][x]=1;

                            }

                        }
                    }


                }
            }
        }

    for(int i=edges.size()-1;i>=0;i--) {
        auto edge = edges[i];
        if(cycle[edge[0]][edge[1]]) {
            return edge;
        }
    }
    return edges[edges.size()-1]; //will never occur
    }

};