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