<p>You are given a <strong>directed</strong> graph of <code>n</code> nodes numbered from <code>0</code> to <code>n - 1</code>, where each node has <strong>at most one</strong> outgoing edge.</p>

<p>The graph is represented with a given <strong>0-indexed</strong> array <code>edges</code> of size <code>n</code>, indicating that there is a directed edge from node <code>i</code> to node <code>edges[i]</code>. If there is no outgoing edge from <code>i</code>, then <code>edges[i] == -1</code>.</p>

<p>You are also given two integers <code>node1</code> and <code>node2</code>.</p>

<p>Return <em>the <strong>index</strong> of the node that can be reached from both </em><code>node1</code><em> and </em><code>node2</code><em>, such that the <strong>maximum</strong> between the distance from </em><code>node1</code><em> to that node, and from </em><code>node2</code><em> to that node is <strong>minimized</strong></em>. If there are multiple answers, return the node with the <strong>smallest</strong> index, and if no possible answer exists, return <code>-1</code>.</p>

<p>Note that <code>edges</code> may contain cycles.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/06/07/graph4drawio-2.png" style="width: 321px; height: 161px;" />
<pre>
<strong>Input:</strong> edges = [2,2,3,-1], node1 = 0, node2 = 1
<strong>Output:</strong> 2
<strong>Explanation:</strong> The distance from node 0 to node 2 is 1, and the distance from node 1 to node 2 is 1.
The maximum of those two distances is 1. It can be proven that we cannot get a node with a smaller maximum distance than 1, so we return node 2.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/06/07/graph4drawio-4.png" style="width: 195px; height: 161px;" />
<pre>
<strong>Input:</strong> edges = [1,2,-1], node1 = 0, node2 = 2
<strong>Output:</strong> 2
<strong>Explanation:</strong> The distance from node 0 to node 2 is 2, and the distance from node 2 to itself is 0.
The maximum of those two distances is 2. It can be proven that we cannot get a node with a smaller maximum distance than 2, so we return node 2.
</pre>

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

<ul>
	<li><code>n == edges.length</code></li>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>-1 &lt;= edges[i] &lt; n</code></li>
	<li><code>edges[i] != i</code></li>
	<li><code>0 &lt;= node1, node2 &lt; n</code></li>
</ul>

class Solution {
public:
    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
        //Idea is to run bfs starting from both nodes, and then store their distances 
        //In 2 separate hashmaps, and compare the minimum of the (x1, x2) of all common nodes 
        int n = edges.size();
        vector<vector<int>> adj(n);
        for (int i=0; i<n; i++){
            if (edges[i]!=-1)
            adj[i].push_back(edges[i]);
        }

        unordered_map<int, int> map1;
        unordered_map<int, int> map2;

        queue<int> q;

        bfs(q, adj, node1, map1);
        while (!q.empty()) q.pop();
        bfs(q, adj, node2, map2);
        int ans = INT_MAX;
        int res = -1;
        for (int i=0; i<n; i++){
            if (map1.find(i)!=map1.end() and map2.find(i)!=map2.end()){
                if (ans > max(map1[i], map2[i])){
                    ans = max(map1[i], map2[i]);
                    res = i;
                }
            }
        }

        return res;

    }

    void bfs(queue<int> q, vector<vector<int>> &adj, int node, unordered_map<int, int> &mp){
        int n = adj.size();
        vector<int> vis(n+1, 0);
        q.push(node);
        vis[node] = 1;

        int lvl = 0;
        while (!q.empty()){
            int cur_node = q.front();
            q.pop();
            mp[cur_node] = lvl;

            for (auto it: adj[cur_node]){
                //cout << it << endl;
                if (vis[it]==0){
                    vis[it] = 1;
                    q.push(it);
                }
            }
            lvl+=1;
        }
        // if (mp.find(1) == mp.end()){
        //     cout << "hi";
        // }
        //for (int i=0; i<n; i++) cout << mp[i] << " ";
    }
};
193540