Giornalismo d’inchiesta

Durante la sua attività giornalistica, Mino incappa in uno scoop.
Ha infatti scoperto l’esistenza di un’associazione che fu fondata e composta da due membri che si conoscevano direttamente.
Tutti gli altri membri furono successivamente reclutati se conoscevano direttamente uno o due garanti facenti già parte dell’associazione.

Mino è riuscito a ricostruire la genesi dell’attuale associazione.
Numerati i suoi membri da 1 a N, ha scritto sul suo taccuino una serie di M coppie di interi.
In particolare, la coppia composta da due interi (I,J) indica che I ha garantito per J o viceversa.
Infatti, Mino non è riuscito a stabilire chi dei due sia entrato per primo nell’associazione: sia (I,J) che (J,I) rappresentano la stessa coppia, anche perché l’ordine di numerazione dei membri non riflette necessariamente quello dell’iscrizione all’associazione (per esempio, non è detto che i membri numero 1 e 2 siano stati i fondatori o che il membro numero N sia l’ultimo arrivato).

Lo scoop di Mino consiste nell’aver trovato le prove di azioni criminali da parte di alcune triadi all’interno dell’associazione.
Una triade è composta da tre membri I, J e K dell’associazione, tali che le coppie (I,J), (I,K) e (J,K) sono tutte presenti nel taccuino di Mino (è lecito supporre che i membri di una triade si siano aiutati reciprocamente, in un qualche ordine, per entrare nell’associazione).

Per stimare il numero di controlli che Mino deve effettuare, aiutatelo a contare efficientemente quante triadi in tutto contiene l’associazione, basandovi sulle coppie trascritte nel suo taccuino e sulla modalità di reclutamento di nuovi membri: per entrare nell’associazione occorre avere conoscenza diretta di uno o due garanti che ne siano già membri.

Dati in Input

Il file input.txt è composto da M+1 righe.

• La prima riga contiene due interi positivi M e N separati da uno spazio: M rappresenta il numero di coppie contenute nel taccuino di Mino e N il numero di membri dell’associazione.
  Tali membri sono numerati da 1 a N.
• Le successive M righe rappresentano le coppie nel taccuino: ciascuna riga è composta da due interi differenti I e J, separati da uno spazio, per indicare la coppia (I,J).

 

Dati in Output

Il file output.txt è composto da una sola riga contenente un intero non negativo che rappresenta il numero totale di triadi in seno all’associazione.

Assunzioni

• 1 ≤ N ≤ 100000
• N-1 ≤ M ≤ 2N-3
• 1 ≤ I, J ≤ N
• Non esistono due righe in input che rappresentano la stessa coppia.
  Notare che (I,J) = (J,I), per cui non è possibile trovarle entrambe in input.

 

Esempi

 

Note

• L’ordine con cui si considerano i membri per definire una triade è irrilevante: per esempio, sia 2, 4, 7 che 4, 7, 2 definiscono la stessa triade e, pertanto, essa deve essere conteggiata una volta soltanto.