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<int> vis(N,0);
        for(auto edge:edges) {
            grid[edge[0]][edge[1]]=1;
            grid[edge[1]][edge[0]]=1;
        }
        vector<vector<int>> cyclic;

        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();
                    vis[i]=1;
                    int c = current.first;
                    int p = current.second;
                    q.pop();
                    for(int i=1;i<N;i++) {
                        if(grid[c][i]==1 ) {
                            if(vis[i]==0) {
                                q.push({i,c});

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

                            }

                        }
                    }


                }
            }
        }
        return cyclic[cyclic.size()-1];

    }
};