<p>In this problem, a tree is an <strong>undirected graph</strong> that is connected and has no cycles.</p>

<p>You are given a graph that started as a tree with <code>n</code> nodes labeled from <code>1</code> to <code>n</code>, with one additional edge added. The added edge has two <strong>different</strong> vertices chosen from <code>1</code> to <code>n</code>, and was not an edge that already existed. The graph is represented as an array <code>edges</code> of length <code>n</code> where <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> indicates that there is an edge between nodes <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code> in the graph.</p>

<p>Return <em>an edge that can be removed so that the resulting graph is a tree of </em><code>n</code><em> nodes</em>. If there are multiple answers, return the answer that occurs last in the input.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/02/reduntant1-1-graph.jpg" style="width: 222px; height: 222px;" />
<pre>
<strong>Input:</strong> edges = [[1,2],[1,3],[2,3]]
<strong>Output:</strong> [2,3]
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/02/reduntant1-2-graph.jpg" style="width: 382px; height: 222px;" />
<pre>
<strong>Input:</strong> edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
<strong>Output:</strong> [1,4]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == edges.length</code></li>
	<li><code>3 &lt;= n &lt;= 1000</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>1 &lt;= a<sub>i</sub> &lt; b<sub>i</sub> &lt;= edges.length</code></li>
	<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>
	<li>There are no repeated edges.</li>
	<li>The given graph is connected.</li>
</ul>

class Solution {
public:
    unordered_map<int,int> vis;
    int t=0;
    vector<vector<int>> cycles;
    // findCycles function
    void findCycles(int i, vector<vector<int>> &adj, stack<int> &s,vector<int>& disc,vector<int>& low,int parent){
        t++;
        vis[i]=t;
        disc[i]=t;
        low[i]=disc[i];
        s.push(i);
        

        // traverse all the connections
        for(int j=0;j<adj[i].size();j++){
            int dst = adj[i][j];
            // no need to consider parent
            if(dst == parent) continue;

            if(!vis[dst]){
                findCycles(dst,adj,s,disc,low,i);
                low[i] = min(low[i],low[dst]);
            }else low[i] = min(low[i],disc[dst]);
        }
        // cout<<"i: "<<i<<" dsc: "<<disc[i]<<" low: "<<low[i]<<endl;
        vector<int> subCycle;
        while(s.size()>0 && low[s.top()] == disc[i]){
            subCycle.push_back(s.top());
            // cout<<s.top()<<" ";
            s.pop();
        }
        cycles.push_back(subCycle);
        // cout<<endl;

    }

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        // articulation points, find cycle
        cycles.clear();
        int n= edges.size();
        // create a graph
        vector<vector<int>> adj(n+1);
        for(auto v: edges){
            adj[v[0]].push_back(v[1]);
            adj[v[1]].push_back(v[0]);
        }
        
        vector<int> disc(n+1,n+1);
        vector<int> low(n+1,n+1);
        stack<int> s;
        findCycles(1,adj,s,disc,low,0);

        int arr[1001][1001] ={0};
        cout<<"Cycle: "<<endl;
        for(auto cycle : cycles){
            
            if(cycle.size()==1|| cycle.size()==0)continue;
            // for(int i=0;i<cycle.size();i++){
            //     cout<<cycle[i]<<" ";
            // }
            // cout<<endl;
            
            for(int i=0;i<cycle.size();i++){
                
                int curr = cycle[i];
                // cout<<"curr: "<<curr<<" i:"<<i<<endl;
                int nxt = cycle[(i+1)%(cycle.size())];
                int prv = cycle[(cycle.size()+i-1)%(cycle.size())];
                // cout<<curr<<" ";
                arr[nxt][curr]=1;
                arr[prv][curr]=1;
                arr[curr][nxt]=1;
                arr[curr][prv]=1;
            }
            cout<<endl;

        }
        vector<int> ans;
        for(auto v : edges){
            if(arr[v[0]][v[1]]){
                ans = v;
            }
        }

        return ans;

        //store the edges of cycle in a map
        // travers input to find the answer
    }
};
21331