W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
There are towns in Byteotia, connected with only roads. Each road directly links two towns. All the roads have the same length and are two way. It is known that every town can be reached from every other town via a route consisting of one or more (direct-link) roads. In other words, the road network forms a tree.
Byteasar, the king of Byteotia, wants three luxury hotels erected to attract tourists from all over the world. The king desires that the hotels be in different towns and at the same distance one from each other.
Help the king out by writing a program that determines the number of possible locations of the hotel triplet in Byteotia.
The first line of the standard input contains a single integer (), the number of towns in Byteotia. The towns are numbered from to .
The Byteotian road network is then described in lines. Each line contains two integers and () , separated by a single space, that indicate there is a direct road between the towns and .
In tests worth of the total point number an additional condition holds.
The first and only line of the standard output should contain a single integer equal to the number of possible placements of the hotels.
For the input data:
7 1 2 5 7 2 5 2 3 5 6 4 5
the correct result is:
5
Explanation: The triplets (unordered) of towns where the hotels can be erected are: , , , , .
Task author: Jacek Tomasiewicz.
<Submit a solution> [0/100]