URI Online Judge | 3158

O Bom Presidente

Por Samuel Eduardo da Silva, IFSULDEMINAS/UFF BR Brazil

Timelimit: 1

Livrolândia é um país que, como o nome já diz, preza pela leitura. Nesta cidade há uma regra universal: toda cidade do país deve ter acesso a bibliotecas. Todos os presidentes que passaram por Livrolândia conseguiram manter esta regra.

Roci é o atual presidente, e fez questão de dar manutenção a todas as bibliotecas do país, além de manter a boa qualidade das estradas entre as cidades, para que cidades que não tem biblioteca, consigam acesso a cidades vizinhas que tenham.

Infelizmente, Roci é muito azarado e, logo em seu mandato, um tornado destruiu todas as bibliotecas e obstruiu todas as estradas de Livrolândia. Agora, o presidente terá que bolar um plano para reconstruir o país, seguindo sua regra universal e com o menor custo possível para as obras.

Livrolândia tem N cidades numeradas de 1 a N. As cidades são conectadas por M estradas bidirecionadas. Uma cidade tem acesso a um biblioteca se:

            O custo para reparar uma estrada é E tolkiens (tolkiens é a moeda de Livrolândia) e o custo para construir uma biblioteca é B tolkiens.

            Dado o mapa de Livrolândia e os custos de reparo e construção, escreva um programa que retorne o custo mínimo para reconstruir o país, seguindo a regra universal, e assim, salve Roci.

Entrada

A primeira linha da entrada contém um inteiro T indicando o número de possíveis mapas.

A segunda linha da entrada contém 4 inteiros, N, M, B e E, número de cidades, número de estradas, custo para construir uma biblioteca e o custo para construir uma estrada, respectivamente.

Depois há M linhas indicando as estradas obstruídas, em que cada uma há dois inteiros X e Y, indicando que há uma estrada que liga a cidade X à cidade Y.

Limites:

 

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.

Saída

Para cada possível mapa, indique o custo mínimo para reconstruir o país.

Exemplo de Entrada Exemplo de Saída

2

3 3 2 1

1 2

3 1

2 3

6 6 2 5

1 3

3 4

2 4

1 2

2 3

5 6

4

12