long roadsAndLibraries(int n, int c_lib, int c_road, vector<vector<int>> cities) {
    if (cities.empty() || c_lib <= c_road) return (long)n * c_lib;

    map<int, stack<int>> cityMap;
    for (vector<int> road : cities) {
        int city1 = road[0], city2 = road[1];
        cityMap[city1].push(city2);
        cityMap[city2].push(city1);
    }

    vector<bool> visited(n + 1, false); 
    long libs = 0, rds = 0;

    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            libs++;
            stack<int> neighbors;
            neighbors.push(i);
            visited[i] = true;

            while (!neighbors.empty()) {
                int curr = neighbors.top();
                neighbors.pop();

                while (!cityMap[curr].empty()) {
                    int neighbor = cityMap[curr].top();
                    cityMap[curr].pop();

                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        neighbors.push(neighbor);
                        rds++;
                    }
                }
            }
        }
    }

    return libs * c_lib + rds * c_road;
}

class Result
{
    // Uses the Union-Find algorithm to find the number of connected components.
    public static long roadsAndLibraries(int n, int c_lib, int c_road, List<List<int>> cities)
    {
        if (c_lib < c_road)
        {
            return (long)c_lib * n;
        }
        
        int[] parents = new int[n+1]; // n+1 because cities are 1-indexed.
        
        // Init with each node as its own parent.
        for (int i = 0; i <= n; i++)
        {
            parents[i] = i;
        }
        
        foreach (List<int> edge in cities)
        {
            Union(edge[0], edge[1], parents);
        }
        
        // Final round up. Now parents points to the root of each component.
        for (int i = 0; i <= n; i++)
        {
            parents[i] = Find(i, parents);
        }
        
        List<int> parentsList = parents.ToList();
        long components = parentsList.Distinct().LongCount() - 1; // -1 because parents[0] doesn't really exist.
        long edges = n - components;
        
        return (components * c_lib) + (edges * c_road);
    }

public static long roadsAndLibraries(int n, int c_lib, int c_road, List<List<Integer>> cities) {
        if(cities.isEmpty() || c_lib <= c_road) return 1L * n * c_lib;
        
        TreeMap<Integer, Stack<Integer>> cityMap = new TreeMap<>();
        for(List<Integer> connection: cities){
            int c1 = connection.get(0), c2 = connection.get(1);
            cityMap.computeIfAbsent(c1, k -> new Stack<>()).add(c2);
            cityMap.computeIfAbsent(c2, k -> new Stack<>()).add(c1);
        }
        
        long libs = n - cityMap.size(), roads = 0L;
        
        while(!cityMap.isEmpty()){
            // Start new cycle
            libs++;
            Stack<Integer> stack = cityMap.pollFirstEntry().getValue();
            while(!stack.isEmpty()) {
                // DFS for connected cities
                int c = stack.pop();
                if(cityMap.containsKey(c)){
                    roads++;
                    stack.addAll(cityMap.remove(c));
                }
            }
        }
        
        return libs * c_lib + roads * c_road;
    }

    public static long roadsAndLibraries(int n, int c_lib, int c_road, List<List<int>> cities)
    {
        if(n == 0) return 0;
        if(c_lib <= c_road) return n * (long)c_lib;
        
        var connections = new Dictionary<int, List<int>>();
        for(int c = 1; c <= n; c++)
        {
            connections[c] = new List<int>();
        }
        foreach(var cityPair in cities)
        {
            connections[cityPair[0]].Add(cityPair[1]);
            connections[cityPair[1]].Add(cityPair[0]);
        }
        
        var queue = new Queue<int>();
        var visited = new HashSet<int>();
        var cost = 0L;
        
        for(int c = 1; c <= n; c++)
        {
            if(visited.Contains(c))
            {
                continue;
            }
            
            cost += c_lib;
            queue.Enqueue(c);
            visited.Add(c);
            while(queue.Count > 0)
            {
                var city = queue.Dequeue();
                foreach(var neighbour in connections[city])
                {
                    if(!visited.Contains(neighbour))
                    {
                        queue.Enqueue(neighbour);
                        visited.Add(neighbour);
                        cost += c_road;
                    }
                }
            }
        }
        return cost;
    }

def roadsAndLibraries(n, c_lib, c_road, cities):
    # if libraries are cheaper we dont need to build roads
    if c_lib < c_road:
        return c_lib * n
    visited = [0] * n
    transport_stack = []
    cities_map = defaultdict(set)
    islands = 0
    # create a graph of road destinations
    # add both ways for bidirectional paths
    for i in cities:
        cities_map[i[0]-1].add(i[1]-1)
        cities_map[i[1]-1].add(i[0]-1)
    # iterate over the list of road edges
    for city in cities_map:
        if visited[city]:
            continue
        # if we have never been at this city before it is a new island
        islands += 1
        transport_stack.append(city)
        # travel the path of the road
        # if we find a new city add it to the stack
        while transport_stack:
            new_destination = transport_stack.pop(-1)
            if not visited[new_destination]:
                visited[new_destination] = 1
                if new_destination in cities_map:
                    for destination in cities_map[new_destination]:
                        if not visited[destination]:
                            transport_stack.append(destination)
		# if we nevered visited after looking at all the roads then it must be an island 
    islands += n - sum(visited)
    roads = n - islands
    # we need 1 road per city and 1 library per island
    result = (roads * c_road) + (c_lib * islands)
    return result