Write some Programme
€8-30 EUR
Paid on delivery
Chess Championship Sites(Python)
The next International Chess Championship is going to take place in Poland. The organizing committee has to choose a suitable site for the Championship. Due to the expected high number of participants and spectators, it seems obvious that any site consisting of just a single town would not not big enough. Therefore, the committee has decided that the site for the entire Championship will consist of three separate towns in the country. For obvious logistic reasons, it is demanded that those tree towns are neighbours of each other. The committe is equipped with a map of the country and they have to produce a list of candidate town triples which satisfy the neighbourhood conditions. The distances between two neighbouring towns are more or less comparable in densely populated Central Europe, therefore, the road mileages are not an issue in the committee's decision process.
Two towns A and B are considered to be neighbours if there exists such road connection between A and B that there is no other town between A and B on this particular road.
Image 1. Town connection schemes depicting input data in Examples bellow. The possible Championship sites in case a) are {0, 1, 3}, {0, 2, 3}, {0, 2, 4}, {0, 4, 3}, {2, 3, 4}. There are 20 possible Championship sites in case b) as any triple of towns represents an acceptable site. There is no acceptable site in case c).
The task
You are given the scheme of road connections between the towns in the country. Find the number of all possible Championship sites.
Input
The first input line contains two integers N and M separated by space. The values indicate (in this order) the number of towns and the number of pairs of neigbour towns in the country. The towns are labeled by integers 0, 1, ..., N−1. Next, there are M text lines, each describe one pair of neighbour towns. The line contains the labels of the towns separated by space. The order of towns in the pair and the order of pairs of towns in the input is arbitrary.
It holds, 1 ≤ N ≤ 250, 1 ≤ M ≤ 20 000.
Output
The output contains one text line with single integer representing the number of possible sites for the Championship in the country. Each site consists of three mutually neighbour towns.
Example 1
Input
5 8
4 0
0 2
0 1
3 2
4 3
4 2
1 3
3 0
Output
5
The data of Example 1 are depicted in Image 1a).
Example 2
Input
6 15
5 4
2 0
3 1
5 1
4 1
5 3
1 0
4 0
4 3
5 2
2 1
3 0
3 2
5 0
4 2
Output
20
The data of Example 2 are depicted in Image 1b).
Example 3
Input
9 12
0 1
0 2
1 3
1 4
2 4
2 5
3 6
4 6
4 7
5 7
6 8
7 8
Output
0
The data of Example 3 are depicted in Image 1c).
Project ID: #10389999
About the project
1 freelancer is bidding on average €24 for this job
