Caccia agli interruttori

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: interruttori.c
• Scarica la traccia in C++: interruttori.cpp
• Scarica la traccia in Python: interruttori.py
• Scarica la traccia in Rust: interruttori.rs

---

Descrizione del problema

Monica ci tiene molto all'ambiente, e quindi nella sua nuova casa ha installato un impianto composto da $N$ lampadine a risparmio energetico di ultima generazione. Queste lampadine sono governate da interruttori di due tipi:

• tipo 1: cambia lo stato della lampadina $z_i$: se è spenta allora la accende, mentre se è accesa allora la spegne;
• tipo 2: cambia lo stato contemporaneamente a due lampadine $x_i$ e $y_i$.

Quindi, per spegnere o accendere una singola lampadina (senza influenzare le altre), potrebbe essere necessario agire su diversi interruttori in sequenza. Questa cosa ha particolarmente entusiasmato Mojito, il suo cagnolino: stufo di riportare sempre il solito bastoncino, trova molto più interessante inseguire gli interruttori per spegnere tutte le lampadine, dopo che Monica gliene ha accesa una!

Purtroppo in questi giorni Monica è molto indaffarata con la preparazione delle gare territoriali, e quindi vorrebbe tenere Mojito impegnato con poco sforzo. Aiutala trovando la lampadina che necessita del maggior numero di interruttori per essere spenta.

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.

Ciascun caso di test è composto da $A+B+1$ righe. La prima riga contiene i tre interi $N$, $A$, $B$ separati da uno spazio: rispettivamente il numero di lampadine, il numero di interruttori di tipo 1 e il numero di interruttori di tipo 2. Ciascuna delle seguenti $A$ righe è composta da un unico intero che rappresenta un interruttore di tipo 1. Le successive $B$ righe sono composte da 2 interi ciascuna che rappresentano un interruttore di tipo 2.

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: x c

dove t è il numero del caso di test (a partire da $1$), x è l'indice della lampadina e c è il numero di interruttori minimo per spegnere tale lampadina. Se ci sono più lampadine che necessitano dello stesso numero minimo di interruttori per essere spente, puoi rispondere con una qualunque di esse.

Assunzioni

• $T=24$, nei file di input che scaricherai saranno presenti esattamente $24$ casi di test.
• $1 \le N, A, B \le 10^5$.
• $0 \le z_i \le N - 1$, per ogni interruttore di tipo 1.
• $0 \le x_i, y_i \le N - 1$, $x_i \neq y_i$, per ogni interruttore di tipo 2.
• Tutti gli interruttori sono diversi.
• È garantito che sia possibile spegnere ogni lampadina.

Esempi di input/output

---

Input:

4

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

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

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

2 2 1
0
1
0 1

---

Output:

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

---

Spiegazione

Nel primo caso d'esempio l'impianto elettrico di Monica è il seguente:

Per spegnere la lampadina 3 devo premere almeno 3 interruttori:

• premendo l'interruttore 3 di tipo 2 spengo la lampadina 3 e accendo la lampadina 2,
• premendo l'interruttore 2 di tipo 2 spengo la lampadina 2 e accendo la lampadina 1,
• premendo l'unico interruttore di tipo 1 spengo la lampadina 1.

---

Nel secondo caso d'esempio l'impianto elettrico di Monica è il seguente:

Per spegnere la lampadina 2 devo premere almeno 3 interruttori, ci sono più modi, uno è il seguente:

• premendo l'interruttore 1 di tipo 2 spengo la lampadina 2 e accendo la lampadina 3,
• premendo l'interruttore 2 di tipo 2 spengo la lampadina 3 e accendo la lampadina 1,
• premendo l'interruttore 2 di tipo 1 spengo la lampadina 1.

---

Nel terzo caso d'esempio l'impianto elettrico di Monica è il seguente:

Per spegnere la prima lampadina bisogna premere tutti e 5 gli interruttori.

---

Nel quarto caso d'esempio l'impianto elettrico di Monica è il seguente:

Sia la prima lampadina che la seconda si possono spegnere con soltanto un interruttore, pertanto entrambe sono soluzioni valide.