Conteggiare il numero di stelle in un grafo
Dato un grafo non orientato con
v vertici e e archi, il tuo compito è calcolare quanti grafi a stella esso contiene.Un grafo a stella è caratterizzato da un vertice centrale connesso a tutti gli altri vertici, mentre ognuno degli altri vertici è collegato soltanto al centro e non a nessun altro vertice.
Input
La prima riga dell’input contiene due interi
v (1 ≤ v ≤ 1000) ed e (1 ≤ e ≤ 10 000).Le
e righe successive contengono coppie di interi v1, v2 (1 ≤ v1, v2 ≤ v) che rappresentano un arco tra v1 e v2.Output
Il programma deve stampare il numero di grafi a stella presenti nel grafo dato.
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