Tomash keeps wandering off and getting lost while he is walking along the streets of Berland. It's no surprise! In his home town, for any pair of intersections there is exactly one way to walk from one intersection to the other one. The capital of Berland is very different!

Tomash has noticed that even simple cases of ambiguity confuse him. So, when he sees a group of four distinct intersections a, b, c and d, such that there are two paths from a to c — one through b and the other one through d, he calls the group a "damn rhombus". Note that pairs (a, b), (b, c), (a, d), (d, c) should be directly connected by the roads. Schematically, a damn rhombus is shown on the figure below: [Image] 

Other roads between any of the intersections don't make the rhombus any more appealing to Tomash, so the four intersections remain a "damn rhombus" for him.

Given that the capital of Berland has n intersections and m roads and all roads are unidirectional and are known in advance, find the number of "damn rhombi" in the city.

When rhombi are compared, the order of intersections b and d doesn't matter.


-----Input-----

The first line of the input contains a pair of integers n, m (1 ≤ n ≤ 3000, 0 ≤ m ≤ 30000) — the number of intersections and roads, respectively. Next m lines list the roads, one per line. Each of the roads is given by a pair of integers a_{i}, b_{i} (1 ≤ a_{i}, b_{i} ≤ n;a_{i} ≠ b_{i}) — the number of the intersection it goes out from and the number of the intersection it leads to. Between a pair of intersections there is at most one road in each of the two directions.

It is not guaranteed that you can get from any intersection to any other one.


-----Output-----

Print the required number of "damn rhombi".


-----Examples-----
Input
5 4
1 2
2 3
1 4
4 3

Output
1

Input
4 12
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

Output
12

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Combinatorics

Complete search


Solutions:
import sys
(n, m) = [int(i) for i in sys.stdin.readline().split()]
to_sets = [set() for _ in range(n)]
from_sets = [set() for _ in range(n)]
for i in range(m):
	(m1, m2) = [int(i) for i in sys.stdin.readline().split()]
	to_sets[m1 - 1].add(m2 - 1)
	from_sets[m2 - 1].add(m1 - 1)
bd_choices_cache = [[0 for _ in range(n)] for _ in range(n)]
for a in range(n):
	for b in to_sets[a]:
		for c in to_sets[b]:
			bd_choices_cache[a][c] += 1
ans = 0
for a in range(n):
	for c in range(n):
		if a == c:
			continue
		bd_choices = bd_choices_cache[a][c]
		ans += bd_choices * (bd_choices - 1) // 2
print(ans)


(n, m) = list(map(int, input().split()))
adj = []
for i in range(n):
	adj.append([])
for i in range(m):
	(a, b) = list(map(int, input().split()))
	adj[a - 1].append(b)
ans = 0
ncr = []
for i in range(n):
	m = {}
	for j in adj[i]:
		for k in adj[j - 1]:
			if k in list(m.keys()):
				m[k] += 1
			else:
				m[k] = 1
	for j in list(m.keys()):
		if j != i + 1:
			ans += m[j] * (m[j] - 1) // 2
print(ans)


(n, e) = list(map(int, input().split()))
dl = {}
for itr in range(1, n + 1):
	dl[itr] = set()
for itr in range(e):
	(a1, a2) = list(map(int, input().split()))
	dl[a1].add(a2)
ans = 0
for i in range(1, n + 1):
	arr = [0] * (n + 1)
	for j in dl[i]:
		for k in dl[j]:
			if i != k:
				arr[k] += 1
	for itr in arr:
		ans += itr * (itr - 1) // 2
print(ans)


from sys import stdin
inp = stdin.readline
(n, m) = map(int, inp().split())
g = {x: [] for x in range(1, n + 1)}
for _ in range(m):
	(a, b) = map(int, inp().split())
	g[a].append(b)
ans = 0
for i in range(1, n + 1):
	d = {}
	for j in g[i]:
		for k in g[j]:
			if k != i:
				d[k] = d.get(k, 0) + 1
	for k in d.values():
		ans += k * (k - 1) // 2
print(ans)


import sys
from collections import defaultdict, Counter
input = sys.stdin.readline
(n, m) = map(int, input().split())
g = defaultdict(list)
for _ in range(m):
	(a, b) = map(int, input().split())
	g[a - 1].append(b - 1)
rhomb = defaultdict(list)
for vert in g.keys():
	for neigh in g.get(vert, []):
		for nexneigh in g.get(neigh, []):
			if nexneigh == vert:
				continue
			rhomb[nexneigh].append(vert)
ans = 0
for arr in rhomb.values():
	c = Counter(arr)
	for el in c:
		ans += c[el] * (c[el] - 1) // 2
print(ans)


l = input().strip().split(' ')
n = int(l[0])
m = int(l[1])
t = m
v = []
for i in range(n + 1):
	v.append([])
while t > 0:
	l = input().strip().split(' ')
	a = int(l[0])
	b = int(l[1])
	v[a].append(b)
	t -= 1
ans = 0
for p in range(1, n + 1):
	gp = {}
	for ch in range(1, n + 1):
		gp[ch] = 0
	for u in v[p]:
		for x in v[u]:
			if x != p:
				gp[x] += 1
	for ch in gp:
		ans += gp[ch] * (gp[ch] - 1) // 2
print(ans)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.stdin = open('input.txt', 'r')
except:
	pass

def pmat(A):
	for ele in A:
		print(*ele, end='\n')
for _ in range(1):
	(n, m) = L()
	g = [[] for i in range(n + 1)]
	for i in range(m):
		(x, y) = L()
		g[x].append(y)
	ans = 0
	for i in range(1, n + 1):
		d = {}
		for imm in g[i]:
			for ele in g[imm]:
				if ele != i and ele != imm:
					d[ele] = d.get(ele, 0) + 1
		for ele in d:
			if d[ele] >= 2:
				ans += d[ele] * (d[ele] - 1) // 2
	print(ans)
endtime = time.time()


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd
from collections import deque
from bisect import bisect_left
(n, m) = map(int, input().split())
graph = {i: set() for i in range(1, n + 1)}
for i in range(m):
	(a, b) = map(int, input().split())
	graph[a].add(b)
count = 0
for i in range(1, n + 1):
	d = {}
	for j in graph[i]:
		for k in graph[j]:
			if k != i:
				if k in d:
					d[k] += 1
				else:
					d[k] = 1
	for k in d:
		count += d[k] * (d[k] - 1) // 2
print(count)