LCC/Moose '19 Contest 3 S4 - Christmas Trees

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 5.0s
Memory limit: 256M

Authors:
Problem type

You are a substitute teacher for a grade 3 class. As the holidays are nearing, you decided to give them a fun task. You printed out a graph, and told them to draw Christmas trees on all the triangles.

As you randomly drew the graph, you don't know how many trees they will draw. So you bring it upon yourself to find out.


Given a bidirectional graph with V vertices and E edges, find the number of triangles (3 length cycles).

Input Specification

The first line will have two integers V, E, the number of vertices and edges in the graph.

The next E lines will contain two integers a\ b denoting an edge between a and b. Vertices are one-indexed.

Constraints

For 20\% of the points, V \le 100
For an additional 30\% of the points, V \le 10,000
For the last 50\% of the points, V, E \le 10^6

Output Specification

Output a single integer, the number of triangles in the graph.

Sample Input 1

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

Sample Output 1

4

Sample Input 2

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

Sample Output 2

4

Comments

There are no comments at the moment.