/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
typedef pair<Node*, Node*> PI; 
class Solution {
public:
    Node* cloneGraph(Node* node) {
        queue<PI> q; 
        Node* res = new Node(node->val); 
        q.push({res, node}); 
        unordered_map<int, int> hash; 
        hash[res->val]++; 
        while (q.size()) {
            int size = q.size(); 
            for (int i = 0; i < size; i++) {
                auto front = q.front(); q.pop(); 
                hash[front.first->val]++; 
                for (auto nei : front.second->neighbors) {
                    auto newNode = new Node(nei->val); 
                    front.first->neighbors.push_back(newNode); 
                    if (!hash[newNode->val])
                        q.push({newNode, nei}); 
                }
            }
        }
        return res; 
    }
};