Triangles in a Planar Graph

Time limit2sMemory limit128 MB

Summary
Count the triangles (3-cycles) in a planar graph with up to 100,000 vertices and 300,000 edges, exploiting the sparse edge bound for efficiency.
Level

Medium7 of 10

Topics
Graph, Hash map, Sorting, Math
Solved
No attempts yet

Problem

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.

Input

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.

Output

Print the number of triangles on the first line.

Examples1

  1. Example 1

    Input
    4 6
1 2
3 1
2 3
4 2
4 1
3 4
    Expected output
    4