void bfs(int start, unordered_map<int, vector<int>>& adjList, unordered_set<int>& vis) {
    queue<int> pq;
    pq.push(start);
    vis.insert(start);
    while (!pq.empty()) {
        auto node = pq.front();
        pq.pop();
        for (auto nbs: adjList[node]) {
            if (vis.find(nbs) == vis.end()) {
                vis.insert(nbs);
                pq.push(nbs);
            }
        }
    }
}
long roadsAndLibraries(int n, int c_lib, int c_road, vector<vector<int>> cities) {
    //edge case c_lib < c_road therefor, it is optimal to build the lib for each city
    if (c_lib <= c_road) return static_cast<long>(n)*c_lib;
    unordered_map<int, vector<int>> adjList;
    // build adjList
    for(auto ct: cities) {
        adjList[ct[0]].push_back(ct[1]);
        adjList[ct[1]].push_back(ct[0]);
    }
    // unvisited list
    unordered_set<int> vis;
    long cost = 0;
    int region = 0;
    // traversal all city
    for (int i=1; i<= n ;i++) {
        if (vis.find(i) == vis.end()) {
            cost += static_cast<long>(c_lib);
            region++;
            // find out all connected path to current cty
            bfs(i,adjList, vis);
        }
    }
    
    // calculate final cost
    // total path = (cities -1) - (region -1) = cities - region
    cost += (vis.size() - region) * static_cast<long>(c_road);
    return cost;
}