Uma Estrada sem Pedágio
Uma companhia precisa visitar alguns postos de manutenção ligados por uma rede de estradas. A rede tem postos e exatamente estradas bidirecionais, formando uma árvore. Atravessar uma estrada custa seu pedágio, que é cobrado a cada travessia.
A equipe começa no posto , deve visitar todos os postos obrigatórios e pode terminar em qualquer posto. Ela pode repetir estradas e visitar postos não obrigatórios.
Antes de sair, a companhia pode escolher no máximo uma estrada para receber isenção permanente: todas as travessias dessa estrada passam a custar zero, em ambos os sentidos. A companhia escolhe a estrada sabendo quais postos são obrigatórios. Também é permitido não conceder nenhuma isenção.
Determine o menor custo total possível da viagem.
Input
A primeira linha contém e .
A segunda linha contém inteiros distintos, os postos obrigatórios. Se , a linha pode estar vazia.
Cada uma das próximas linhas contém , e , indicando uma estrada bidirecional de pedágio .
Output
Imprima um único inteiro: o menor custo da viagem.
Samples
Sample 1
Input
3 1 3 1 2 5 2 3 7
Output
5
A equipe isenta a estrada de pedágio 7 e percorre 1, 2, 3, pagando somente 5.
Sample 2
Input
3 2 2 3 1 2 5 1 3 7
Output
5
Isentando a estrada entre 1 e 3, a equipe visita o posto 3 sem custo, retorna a 1 e termina em 2.
Sample 3
Input
1 0
Output
0
Não há postos obrigatórios a visitar.