Algorithms and Data Structures

Count the Number of Stars in a Graph

Given an undirected graph with v vertices and e edges, you are asked to count the number of star graphs it contains.

A star graph is a graph that has a central vertex that is connected to all the other vertices, while all the other vertices are only connected to the central one and no other vertex.

profound.academy-graphs-star-graph.drawio.png

Input

The first line of the input contains two integers v (1 ≤ v ≤ 1000) and e (1 ≤ e ≤ 10 000).

The following e lines contain pairs of integers v1, v2 (1 ≤ v1, v2 ≤ v) representing an edge between v1 and v2.

Output

The program should print the number of star graphs in the given graph.

Examples

Input

Output

7 6
1 5
2 5
3 5
7 5
6 5
4 5

1

8 7
1 5
2 5
3 5
7 5
6 5
4 5
1 8

0

8 6
1 2
2 3
4 2
5 6
7 6
8 6

2

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue