Uma estrada a mais
Há vilas, e a vila tem moradores. As estradas existentes são bidirecionais e formam uma árvore. Você construirá exatamente uma nova estrada entre duas vilas distintas. É permitido construir uma segunda estrada entre vilas que já eram vizinhas; as duas estradas são independentes.
Um par de moradores de vilas diferentes é protegido se, após a construção, eles continuam conectados mesmo que qualquer uma das estradas seja interditada. A interdição é de uma única estrada por vez, podendo incluir a nova estrada.
Escolha a nova estrada para maximizar a quantidade de pares protegidos. Pares não são ordenados, e todos os moradores são distintos. Não conte pares de moradores da mesma vila.
Input
A primeira linha contém (). A segunda contém (). Cada uma das próximas linhas contém (), descrevendo uma estrada. O grafo dado é uma árvore.
Output
Imprima a maior quantidade de pares protegidos.
Samples
Sample 1
Input
4 1 2 3 4 1 2 1 3 1 4
Output
19
Ligue as vilas 3 e 4. As vilas 3, 1 e 4 ficam no ciclo, protegendo 3×1 + 3×4 + 1×4 = 19 pares.
Sample 2
Input
2 5 7 1 2
Output
35
Uma segunda estrada entre as duas vilas protege todos os 35 pares entre elas.