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.
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