void insertCityToMap(std::map<long, vector<long>> &cityMap, int &cityNum1, int &cityNum2){
    std::map<long, vector<long>>::iterator it = cityMap.find(cityNum1);
        if(it == cityMap.end()){ //insert new vector
            cityMap.insert(pair<long, vector<long>>(cityNum1, vector<long>{cityNum2}));
        }else{
            if(find(it->second.begin(), it->second.end(), cityNum2) == it->second.end()) //sanity check incase of duplicate
            it->second.push_back(cityNum2);
        }
}

//arguments passed by reference
void cityDfs(std::map<long, vector<long>> &cityMap, long &adj, std::vector<bool> &visited, long &minCost, int &c_road, int &count){
    minCost += c_road;
    visited[adj] = true;
    count++;
    std::map<long, vector<long>>::iterator it = cityMap.find(adj);
    std::vector<long> connectedCities = it->second;
    for(long long i=0; i<connectedCities.size(); i++){
        if(visited[connectedCities[i]] == false){
            cityDfs(cityMap, connectedCities[i], visited, minCost, c_road, count);    
        }
    }
}

long roadsAndLibraries(int n, int c_lib, int c_road, vector<vector<int>> cities) {
    if(c_lib <= c_road){
        return long(c_lib*n);
    }
    
    std::map<long, vector<long>> cityMap;
    std::vector<bool> visited(n+1, false);
    
    for(long i=0; i<cities.size(); i++){
        insertCityToMap(cityMap, cities[i][0], cities[i][1]);
        insertCityToMap(cityMap, cities[i][1], cities[i][0]);
    }
    
    std::map<long, vector<long>>::iterator it;
    long minCost = 0;
    int count = 0; //to track the number of visted cities. This will help when identifying the number of standalone cities.
    
    //starting with a map node (city), it will build one library and DFS to complete the rest of the sub-map.
    for(it=cityMap.begin(); it != cityMap.end(); it++){
        if(visited[it->first] == false){
            minCost += c_lib; 
            visited[it->first] = true;
            count++;
            for(long long j=0; j < it->second.size(); j++){
                if(visited[it->second[j]] == false){
                    cityDfs(cityMap, it->second[j], visited, minCost, c_road, count);   
                }
            }
        }
    }
    
    return minCost+c_lib*(n-count);
}