Film Festival

Time limit1sMemory limit128 MB

Summary
Given a bipartite graph of boat connections, count the number of pairs of left villages and pairs of right villages that form a complete K2,2 subgraph.
Level

Medium5 of 10

Topics
Combinatorics, Hash map, Graph
Solved
No attempts yet

Problem

A wide river separates two groups of villages. There are N villages on the left side and N villages on the right side, and each side is numbered from 1 to N. There are M boats, each directly connecting one left-side village and one right-side village. Every boat can be used in both directions.

Sanggeun wants to hold a film festival in four villages. He will choose 2 villages on the left side and 2 villages on the right side. Each chosen left-side village must be directly connected by boat to each chosen right-side village.

Find the number of ways to choose the four villages for the festival.

Input

The first line contains the number of villages N and the number of boats M. (2 \le N \le 1000, 4 \le M \le N^2)

Each of the next M lines contains two village numbers connected by a boat, in the order left-side village then right-side village.

Output

Print the number of ways to choose the four villages for the festival.

Examples2

  1. Example 1

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

  2. Example 2

    Input
    3 7
1 1
1 3
2 1
2 3
3 1
3 2
3 3
    Expected output
    3