Percorso palindromo

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: palindromo.c
• Scarica la traccia in C++: palindromo.cpp
• Scarica la traccia in Python: palindromo.py
• Scarica la traccia in Java: palindromo.java
• Scarica la traccia in C#: palindromo.cs
• Scarica la traccia in JavaScript: palindromo.html
• Scarica la traccia in JavaScript (Node.js): palindromo.js

Descrizione del problema

Per festeggiare i 40 anni di Monica, Mojito le ha preparato una sorta di caccia al tesoro.

Come ben noto, l'infrastruttura di Milano (la città dove vive Monica) è formata da $N$ incroci, numerati da $0$ a $N - 1$, e da $M$ strade bidirezionali numerate da $0$ a $M - 1$ che collegano tali incroci. La $i$-esima strada collega gli incroci $A_i$ e $B_i$.

Mojito ha disseminato una pallina in ciascuna delle $M$ strade. Su ogni pallina è impressa una lettera: in particolare, la pallina posta nella $i$-esima strada reca la lettera $L_i$.

L'obiettivo di Monica è andare (a piedi) dal suo appartamento, che si trova all'incrocio $X$, all'incrocio $Y$ in cui la aspetta Mojito. Ogni volta che percorre una strada, Monica deve segnare su un foglio la lettera scritta sulla pallina che si trova in quella strada (lasciando la pallina dov'è). Quando raggiunge Mojito, Monica avrà vinto se sul foglio è scritta una parola palindroma (una parola si dice palindroma quando rimane invariata se la si legge al contrario).

Aiuta Monica a vincere il gioco percorrendo il minimo numero possibile di strade, per evitare di infrangere il coprifuoco!

Nota: Il percorso di Monica può passare più volte da uno stesso incrocio o anche da una stessa strada.

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+2$ righe:

• la prima riga contiene i due interi $N$ e $M$, il numero di incroci e il numero di strade.
• la seconda riga contiene i due interi $X$ e $Y$, l'incrocio di partenza e l'incrocio di destinazione.
• le successive $M$ righe contengono ciascuna i due interi $A_i$, $B_i$ e il carattere $L_i$ che rappresentano l'$i$-esima strada.

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: s

dove t è il numero del caso di test (a partire da $1$) e il valore s è la lunghezza minima di un percorso palindromo tra $X$ e $Y$. Se tale percorso non esiste, s deve valere $-1$.

Assunzioni

• $T = 24$, nei file di input che scaricherai saranno presenti esattamente $24$ casi di test.
• $1 \le N \le 300$.
• $1 \le M \le 300$.
• $0 \le X,Y \le N-1$.
• $0 \le A_i,B_i \le N-1$ per ogni $0 \le i \le M-1$.
• $L_i$ è una lettera minuscola dell'alfabeto inglese (a-z) per ogni $0 \le i \le M-1$.
• Per ogni coppia di incroci esiste al più una strada che li collega, e non esistono strade che iniziano e terminano nello stesso incrocio. Tutte le strade possono essere percorse in qualsiasi direzione.

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

• Tutte le lettere $L_i$ sono uguali.

Esempi di input/output

---

Input:

3

5 5
0 4
0 1 b
1 3 c
0 2 a
2 1 c
3 4 a

6 5
3 4
0 5 a
4 5 a
3 1 z
2 3 a
0 3 b

4 3
0 2
0 1 o
1 2 i
2 3 i

---

Output:

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

---

Spiegazione

Nel primo caso d'esempio il percorso palindromo di lunghezza minima tra i nodi $0$ e $4$ è $0 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 4$, che compone la parola acca. Esiste un percorso più breve, $0 \rightarrow 1 \rightarrow 3 \rightarrow 4$, che passa per $3$ strade ma non è palindromo e quindi non risulta valido.

Nel secondo caso d'esempio la soluzione è il percorso palindromo $3 \rightarrow 2 \rightarrow 3 \rightarrow 0 \rightarrow 5 \rightarrow 4$, per un totale di $5$ strade percorse, che compone la parola aabaa. Si noti come questo percorso passa due volte per la strada che collega gli incroci $2$ e $3$.

Nel terzo caso d'esempio, qualunque percorso che collega gli incroci $0$ e $2$ inizia con la lettera o e termina con la lettera i, e pertanto non può essere palindromo.