Triangles in a Planar Graph

You are given a planar graph with N vertices, where 1 <= N <= 100,000. Write a program that determines how many triangles, that is, cycles of length 3, exist in the graph.

A planar graph is a graph that can be drawn on a plane so that no two edges cross.

For three distinct vertices x, y, and z, if all three edges x-y, y-z, and z-x exist, then these three vertices form a triangle.

The vertices are numbered from 1 to N.

The first line contains two integers N and M. M is the number of edges and satisfies 0 <= M <= 300,000.

Each of the next M lines contains the numbers of two distinct vertices connected by an edge. No edge appears more than once, and all edges are undirected.

Print the number of triangles on the first line.