Training - Espansione del danno

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: espanditutto.c

Scarica la traccia in C++: espanditutto.cpp

Scarica la traccia in C#: espanditutto.cs

Scarica la traccia in Go: espanditutto.go

Scarica la traccia in JavaScript: espanditutto.html

Scarica la traccia in Java: espanditutto.java

Scarica la traccia in Pascal: espanditutto.pas

Scarica la traccia in Python: espanditutto.py

Scarica la traccia in VisualBasic: espanditutto.vb

Descrizione del problema

Noemi ha un bellissimo monitor i cui $N \times M$ pixel sono organizzati su $N$ righe e $M$ colonne. Ogni pixel è indicato da una coppia di indici $(R_i, C_i)$ : il pixel in alto a sinistra è indicato dalla coppia $(1, 1)$ , quello in basso a destra dalla coppia $(N, M)$ . Un giorno Noemi nota che purtroppo $P$ pixel sono bruciati. Noemi sa che un danno del genere nasce e si espande nel seguente modo: uno stesso giorno alcuni pixel si bruciano spontanamente; da quel giorno, ogni giorno si bruciano anche i pixel adiacenti (cioè con un lato in comune) a quelli che si sono bruciati nei giorni precedenti.

"img"

Noemi vuole capire quanti giorni fa al massimo si sono bruciati i primi pixel, la sapresti aiutare?

Attenzione: in tutti i gruppi di test, eccetto l'ultimo, i pixel bruciati non toccano il bordo del monitor.

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 $P$ , $N$ , $M$ .
$P$ righe, la $i$ -esima contenente i due interi $R_{i}$ , $C_{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 $\mathtt{ris}$ .

Assunzioni

$T = 20$ , nei file di input che scaricherai saranno presenti esattamente $20$ casi di test.
$1 \leq P \leq 10^5$ .
$1 \leq R_i \leq N \leq 10^5$ , dove $R_i$ è l'indice di riga dell' $i$ -esimo pixel bruciato fornito nell'input.
$1 \leq C_i \leq M \leq 10^5$ , dove $C_i$ è l'indice di colonna dell' $i$ -esimo pixel bruciato fornito nell'input.
in tutti i gruppi di test, eccetto l'ultimo, i $P$ pixel bruciati non toccano il bordo del monitor.

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 N = 1 & 1, 2 \\ \hline \text{il danno è stato creato da un solo pixel} & 3, 4 \\ \hline P \leq 100 & 5, 6 \\ \hline P \leq 10^5 & 7, 8 \\ \hline \text{Nessuna assunzione aggiuntiva} & 9, 10 \\ \hline \end{array}$

Esempi di input/output

Input:

Output:

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

Spiegazione

Nel primo caso di esempio, il danno attuale osservato da Noemi corrisponde al danno iniziale. Quindi il danno è stato fatto oggi! Il numero scritto in ognuno dei pixel bruciati indica il giorno in cui il pixel si è bruciato.

"es1"

Nel secondo caso di esempio, il danno iniziale interessava il solo pixel $(4,4)$ . In un solo giorno sono poi stati coinvolti i 4 pixel ad esso adiacenti. Il numero scritto in ognuno dei pixel bruciati indica il giorno in cui il pixel si è bruciato.

"es2"

Nel terzo caso di esempio il danno che Noemi vede sul suo monitor potrebbe essere stata causata $4$ giorni se il pixel in $(1, 10)$ si fosse bruciato o anche $3$ giorni se il pixel in $(1, 9)$ si fosse bruciato. I primi pixel si sono bruciati al più $4$ giorni fa e il danno non sarebbe potuto avvenire prima. Il numero scritto in ognuno dei pixel bruciati indica il giorno in cui il pixel si è bruciato.

"es3"

Nel quarto caso di esempio il danno che Noemi vede sul suo monitor è il seguente:

"es4"