Duas interdições
Uma rede tem estações e ligações não direcionadas, numeradas de a . Ligações diferentes podem ter as mesmas extremidades, mas nenhuma liga uma estação a ela mesma.
A rede é conexa e o grau de cada estação é par. Assim, antes de qualquer interdição, é possível percorrer todas as ligações exatamente uma vez e voltar à estação inicial.
Serão interditadas exatamente duas ligações distintas. Depois disso, queremos que ainda seja possível percorrer todas as ligações restantes exatamente uma vez, em um único percurso. As estações inicial e final podem ser escolhidas livremente e podem ser diferentes. Estações que ficarem sem ligações não precisam ser visitadas.
Quantos pares não ordenados de ligações podem ser interditados mantendo essa possibilidade? Ligações paralelas são distintas e podem formar um par.
Input
A primeira linha contém e (, ).
Output
Imprima um inteiro: a quantidade de pares que podem ser interditados.
Samples
Sample 1
Input
4 4 1 2 2 3 3 4 4 1
Output
4
As duas ligações interditadas devem ter uma extremidade em comum. A estação entre elas fica isolada, o que é permitido.
Sample 2
Input
3 4 1 2 1 2 2 3 2 3
Output
6
Todos os seis pares são válidos, inclusive os pares formados por duas ligações paralelas.