Gruppo vacanze

Per aiutarti con questo task, abbiamo preparato delle tracce di soluzione, che includono solo le parti di lettura dell'input e scrittura dell'output (da tastiera e su schermo). Puoi decidere se leggere/scrivere su file decommentando le opportune righe di codice.

• Scarica la traccia in C: vacanze.c
• Scarica la traccia in C++: vacanze.cpp
• Scarica la traccia in Python: vacanze.py
• Scarica la traccia in Java: vacanze.java
• Scarica la traccia in C#: vacanze.cs
• Scarica la traccia in JavaScript: vacanze.html
• Scarica la traccia in JavaScript (Node.js): vacanze.js

Descrizione del problema

Alessandro ha vinto alla lotteria un pacchetto all-inclusive per una vacanza a Budapest per quattro persone! Sfortunatamente, i suoi numerosi impegni non gli permettono di andare in vacanza. Per questo ha deciso di individuare, fra i suoi conoscenti, un gruppo di quattro persone a cui regalare la vacanza.

Alessandro ha $N$ conoscenti, numerati da $0$ a $N - 1$. Alcuni di essi sono amici fra loro. In particolare, fra i conoscenti di Alessandro esistono $M$ coppie di amici (l'amicizia è sempre reciproca: se $A$ è amico di $B$, anche $B$ è amico di $A$ e viceversa).

Secondo Alessandro, un gruppo di 4 persone è un gruppo vacanza perfetto se ognuno di loro ha già due amici nel gruppo, ma anche una persona nuova con cui fare amicizia (in altre parole, se ciascuno dei quattro membri è amico di esattamente due degli altri tre).

Aiutalo a contare quanti sono tutti i gruppi vacanza perfetti possibili fra i suoi conoscenti.

Dati di input

La prima riga del file di input contiene un intero $T$, il numero di casi di test. Seguono $T$ casi di test, numerati da $1$ a $T$. Ogni caso di test è preceduto da una riga vuota.

Ogni caso di test è composto da $M + 1$ righe:

• la prima riga contiene gli interi $N$ e $M$;
• la $i$-esima ($0 \le i < M$) delle successive $M$ righe contiene due interi $A_i$ e $B_i$, a significare che le persone $A_i$ e $B_i$ sono amici.

Dati di output

Il file di output deve contenere la risposta ai casi di test che sei riuscito a risolvere. Per ogni caso di test che hai risolto, il file di output deve contenere una riga con la dicitura:

Case #t: g

dove t è il numero del caso di test (a partire da $1$) e il valore g è il numero di gruppi vacanza perfetti possibili.

Assunzioni

• $T = 19$, nei file di input che scaricherai saranno presenti esattamente $19$ casi di test.
• $4 \le N \le 1500$.
• $0 \le M \le 3000$.
• $0 \le A_i, \, B_i < N$ per $i = 0, \, \dots, \, M - 1$.
• $A_i \ne B_i$ per $i = 0, \, \dots, \, M - 1$ (nessuna persona è amica di se stessa).
• Le $M$ coppie di amici sono tutte distinte.

Nei primi $8$ casi di test valgono le seguenti assunzioni aggiuntive:

• $N \le 50$.
• $M \le 1000$.

Note

• Due gruppi vacanza contano come diversi se c'è almeno una persona che appartiene al primo gruppo ma non al secondo. Cioè, l'ordine delle persone all'interno di un gruppo non è importante.

Esempi di input/output

---

Input:

3

5 6
4 0
3 4
1 2
1 4
3 2
0 2

4 6
0 1
0 2
0 3
1 2
1 3
2 3

7 15
2 3
6 0
3 4
2 6
3 5
5 2
6 4
2 0
2 1
4 1
4 5
0 5
6 1
5 6
3 0

---

Output:

Case #1: 3
Case #2: 0
Case #3: 4

---

Spiegazione

Nel primo caso d'esempio, le $M = 6$ relazioni di amicizia tra gli $N = 5$ conoscenti di Alessandro sono mostrate in figura (a), dove le persone sono indicate da un cerchio e le amicizie da linee.

Ci sono $3$ possibili gruppi vacanza perfetti: $\{0, \, 2, \, 3, \, 4\}$, $\{0, \, 1, \, 2, \, 4\}$ e $\{1, \, 2, \, 3, \, 4\}$, mostrati rispettivamente nelle figure (b), (c) e (d).

Nel secondo caso d'esempio, ci sono $N = 4$ persone e sono tutte amiche tra loro. Pertanto, è impossibile selezionare un gruppo di quattro persone come richiesto, perché ciascuno sarebbe amico di tutti e tre gli altri membri del gruppo.

Nel terzo caso d'esempio, ci sono $N = 7$ persone e $M = 15$ relazioni di amicizia. In totale ci sono $4$ possibili gruppi vacanza perfetti.