Voci di corridoio

Attenzione: Questo task ha un tempo limite di 10 minuti per l'invio della soluzione. Una volta richiesto un input, il timer partirà in automatico, e dopo la scadenza non sarà più possibile inviare una soluzione per quell'input. È sempre possibile richiedere un nuovo input, per cui non preoccuparti se il timer scade: dovrai semplicemente richiedere e scaricare un nuovo input.

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: gossip.c
• Scarica la traccia in C++: gossip.cpp
• Scarica la traccia in C#: gossip.cs
• Scarica la traccia in Go: gossip.go
• Scarica la traccia in JavaScript (HTML): gossip.html
• Scarica la traccia in Java: gossip.java
• Scarica la traccia in JavaScript (wasm-ide): gossip.js
• Scarica la traccia in Pascal: gossip.pas
• Scarica la traccia in Python: gossip.py
• Scarica la traccia in VisualBasic: gossip.vb

Descrizione del problema

Iniziano già a girare voci tra i partecipanti su chi sarà il prossimo vincitore delle Olimpiadi Italiane di Informatica.

Tra gli $N$ partecipanti delle OII, numerati da $0$ a $N-1$, ci sono $M$ amicizie, l'$i$-esima delle quali stabilisce che le persone $A_i$ e $B_i$ sono amiche. La rete delle amicizie è connessa: per ogni coppia di partecipanti esiste almeno una catena di amicizie che le collega.

Il primo giorno nascono $K$ pettegolezzi, numerati da $0$ a $K-1$: l'$i$-esimo dei quali viene lanciato dalla persona $G_i$, che crede fin da subito a quel pettegolezzo.

Nei giorni successivi, chiunque creda a un pettegolezzo lo condivide con i propri amici. Durante ogni giornata, i pettegolezzi vengono condivisi in ordine di indice: prima il pettegolezzo $0$, poi l'$1$, e così via fino al $K-1$.

I partecipanti sono molto prevedibili: credono solo al primo pettegolezzo che sentono. Una volta convinti di un pettegolezzo, lo condivideranno a partire dal giorno successivo e ignoreranno tutti gli altri.

Dopo un certo numero di giorni ogni partecipante crederà a un pettegolezzo e le voci smetteranno di diffondersi.

Stabilisci per ognuno degli $N$ partecipanti a quale pettegolezzo crederà una volta che le voci si saranno diffuse completamente.

Attenzione: per evitare file di output di grandi dimensioni, dovrai stampare il risultato come segue.

Detto $P_i$ il pettegolezzo a cui alla fine crederà l'$i$-esimo partecipante, stampa $\sum_{i = 0}^{N - 1}{P_i \cdot (i + 1)}$

ovvero la somma dei pettegolezzi finali, ciascuno moltiplicato per l'indice del partecipante aumentato di $1$.

Attenzione: questa quantità è troppo grande per essere rappresentata con un intero a 32 bit, ricordati di utilizzare un tipo di intero ad almeno 64 bit.

Formato 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 come segue:

• una riga contenente i tre interi $N$, $M$, $K$.
• una riga contenente gli $K$ interi $G_{0}, \, \ldots, \, G_{K-1}$.
• $M$ righe, la $i$-esima contenente i due interi $A_{i}$, $B_{i}$.

Formato 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 #test: ", dove test è il numero del caso di test (a partire da $1$), seguita dall'intero a 64 bit $\mathtt{ris}$.

Assunzioni

• $T = 20$, nei file di input che scaricherai saranno presenti esattamente $20$ casi di test.
• $1 \le K \le N \le 10^5$.
• $1 \le M \le 10^5$.
• $0 \le G_{i} \le N - 1$, per ogni $i$ tale che $0 \le i \le K-1$.
• $0 \le A_{i}, B_{i} \le N - 1$, per ogni $i$ tale che $0 \le i \le M-1$.
• Le coppie di amicizie sono tutte distinte.
• Non esistono persone amiche di se stesse.
• Le amicizie formano un grafo connesso.

Gruppi di testcase:

I casi di test sono suddivisi in 10 gruppi.
Ogni gruppo vale 5 punti che vengono ottenuti se si risolvono correttamente tutti i testcase del gruppo. Gruppi diversi possono contenere testcase rispondenti alle stesse assunzioni.

$\small \def\arraystretch{1.5} \begin{array}{|c|c|} \hline \texttt{Assunzioni} & \texttt{Gruppi} \\ \hline K = 2, A_{i} = i, B_{i} = i+1, \text{per ogni } 0 \leq i \leq N-1 & 1, 2 \\ \hline A_{i} = i, B_{i} = i+1, \text{per ogni } 0 \leq i \leq N-1 & 3, 4, 5 \\ \hline N \leq 5000, M \leq 5000 & 6, 7, 8 \\ \hline \text{Nessuna assunzione aggiuntiva} & 9, 10 \\ \hline \end{array}$

Esempi di input/output

---

Input:

4

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

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

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

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

---

Output:

Case #1: 8
Case #2: 5
Case #3: 9
Case #4: 29

---

Spiegazione

Nel primo caso d'esempio il grafo dei pettegolezzi inizialmente è il seguente:

I pettegolezzi vengono condivisi nel seguente modo:

• Dopo un giorno il partecipante $0$ inizia a credere al pettegolezzo $0$, condiviso dal partecipante $4$.
• Dopo due giorni anche il partecipante $3$ inizia a credere al pettegolezzo $0$.

Il grafo finale è dunque il seguente:

Dunque, i partecipanti crederanno rispettivamente ai pettegolezzi $[0, 1, 2, 0, 0]$. L'intero da stampare è dunque $0 \cdot 1 + 1 \cdot 2 + 2 \cdot 3 + 0 \cdot 4 + 0 \cdot 5 = 8$.

Nel secondo caso d'esempio il grafo inizialmente è il seguente:

I pettegolezzi vengono condivisi nel seguente modo:

• Dopo un giorno il partecipante $3$ inizia a credere al pettegolezzo $0$, e il partecipante $2$ inizia a credere al pettegolezzo $1$.
• Dopo due giorni il partecipante $0$ inizia a credere al pettegolezzo $0$.

Il grafo finale è dunque il seguente:

Dunque, i partecipanti crederanno rispettivamente ai pettegolezzi $[0, 1, 1, 0, 0]$. L'intero da stampare è dunque $0 \cdot 1 + 1 \cdot 2 + 1 \cdot 3 + 0 \cdot 4 + 0 \cdot 5 = 5$.

Nel terzo caso di esempio, quando nessun pettegolezzo si starà più spargendo, i partecipanti crederanno rispettivamente ai pettegolezzi $[0, 0, 0, 1, 1]$. L'intero richiesto è quindi $0 \cdot 1 + 0 \cdot 2 + 0 \cdot 3 + 1 \cdot 4 + 1 \cdot 5 = 9$.

Nel quarto caso di esempio, quando nessun pettegolezzo si starà più spargendo, i partecipanti crederanno rispettivamente ai pettegolezzi $[1, 1, 0, 0, 0, 2, 2]$. L'intero richiesto è quindi $1 \cdot 1 + 1 \cdot 2 + 0 \cdot 3 + 0 \cdot 4 + 0 \cdot 5 + 2 \cdot 6 + 2 \cdot 7 = 29$.