The Good President
Exercício de Projeto e Análise de Algoritmos
Enunciado Beecrowd (URI):
Livrolândia is a country that, as the name says, values reading. In this city there is a universal rule: every city in the country must have access to libraries. All presidents who passed through Livrolândia managed to maintain this rule.
Roci is the current president, and made a point of maintaining all libraries in the country, in addition to maintaining the good quality of roads between cities, so that cities that do not have a library, gain access to neighboring cities that do.
Unfortunately, Roci is very unlucky, and as early as his tenure, a tornado destroyed all libraries and obstructed all roads in Livroland. Now, the president will have to come up with a plan to rebuild the country, following his universal rule and at the lowest possible cost for the works.
Livrolândia has N cities numbered 1 to N. The cities are connected by M two-way roads. A city has access to a library if:
This city has a library;
It is possible, from this city, to travel to a city that contains a library.
The cost to repair a road is E tolkiens (tolkiens is the currency of Livroland) and the cost to build a library is B tolkiens.
Given the map of Livrolândia and the costs of repair and construction, write a program that returns the minimum cost to rebuild the country, following the universal rule, and thus save Roci.
Input
The first line of the entry contains an integer T indicating the number of possible maps.
The second line of the entry contains 4 integers, N, M, B and E, number of cities, number of roads, cost to build a library and cost to build a road, respectively.
Then there are M lines indicating the blocked roads, each of which has two integers X and Y, indicating that there is a road that connects city X to city Y.
Limits: 1 <= T <= 10;
1 <= N <= 10 ^ 5;
0 <= M <= min (10 ^ 5, (N * (N-1)) / 2);
1 <= B, E <= 10 ^ 5;
1 <= X, Y <= N.
Output
For each possible map, indicate the minimum cost to rebuild the country.