Wesley's Anger Contest Reject 1 - Stupendous Bowties 2

View as PDF

Submit solution

Points: 17
Time limit: 2.0s
Memory limit: 256M

Problem types

A Fantastic Right Triangle is a subgraph which uses 3 distinct vertices and 3 distinct edges, such that each pair of vertices has exactly 1 edge connecting them.

A Stupendous Bowtie consists of an unordered pair of Fantastic Right Triangles which share exactly one vertex. Count the number of Stupendous Bowties in the given graph with N vertices and M edges.

Below is an example of a Stupendous Bowtie:


For this problem, you will be required to pass all the samples in order to receive points.

5 \le N \le 300\,000
6 \le M \le 300\,000
1 \le a_i, b_i \le N
a_i \neq b_i and each pair of distinct vertices are connected by at most one edge.

Input Specification

The first line contains two space-separated integers N and M.

M lines follow; the i^\text{th} one contains two space-separated integers a_i, b_i indicating that vertices a_i and b_i are connected by an edge.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output the number of Stupendous Bowties in the given graph on a single line.

Sample Input 1

5 6
1 2
2 3
3 1
3 4
3 5
4 5

Sample Output 1


Sample Input 2

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

Sample Output 2



There are no comments at the moment.