Problem: consistency_ch2 (2021 quals)

**Note: This problem shares similarities with [Chapter 1](https://www.facebook.com/codingcompetitions/hacker-cup/2021/qualification-round/problems/A1). The solution to either chapter may help with solving the other, so please consider reading both first.**

Connie received a string \(S\) for her birthday, consisting entirely of uppercase letters (each between `"A"` and `"Z"`, inclusive).

However, Connie really only likes nice, *consistent* strings. She considers a string to be consistent if and only if all of its letters are the same.

Each second, Connie may choose one letter in \(S\) and replace it with a different letter. **There are \(K\) different types of replacements she may make, with the \(i\)th one involving choosing letter \(A_i\) anywhere in \(S\) and replacing it with letter \(B_i\).** No type of replacement (ordered pair of \(A_i\) and \(B_i\)) is given twice. There is no limit on how many times she may end up using each type of replacement. If a letter appears multiple times in \(S\), she may only replace a single occurrence per second.

Help her determine the minimum number of seconds required to change \(S\) into any consistent string, if possible. If it's impossible to ever do so, output \(-1\) instead. Note that \(S\) might already be consistent, in which case \(0\) seconds would be required.

# Constraints

\(1 \le T \le 40\)
\(1 \le |S| \le 100\)
\(0 \le K \le 300 \)
`"A"` \(\le S_i, A_i, B_i \le\) `"Z"`
\(A_i \ne B_i\)

The sum of \(|S|\) across all test cases is at most \(4{,}000\).




# Input

Input begins with an integer \(T\), the number of birthdays Connie has had. For each birthday, there is one line containing the string \(S\), then another line containing the integer \(K\), then \(K\) more lines, the \(i\)th of which contains the two characters \(A_i\) and \(B_i\).


# Output

For the \(i\)th string, print a line containing *"Case #i: "* followed by the minimum number of seconds required to change \(S\) into any consistent string, or \(-1\) if it's impossible to do so.


# Sample Explanation

In the first case, Connie could replace the second and third letters (`"B"` and `"C"`) each with `"A"`, yielding the string `"AAA"` in \(2\) seconds.

In the second case, Connie cannot apply either available type of replacement to `"ABC"`, meaning that she cannot change it into a consistent string.

In the third case, `"F"` is already consistent.

In the fourth case, Connie could replace the first, third, and fifth letters (`"B"`, `"N"`, and `"N"`) each with `"A"`, yielding the string `"AAAAAA"` in \(3\) seconds.

In the sixth case, Connie could change "`FOXEN"` into the string `"WWWWW"` in \(8\) seconds. Note that she may apply a sequence of multiple replacements to any of the letters in \(S\).


Sample input:
7
ABC
2
BA
CA
ABC
2
AB
AC
F
0
BANANA
4
AB
AN
BA
NA
FBHC
4
FB
BF
HC
CH
FOXEN
8
NI
OE
NX
EW
OI
FE
FN
XW
CONSISTENCY
26
AB
BC
CD
DE
EF
FG
GH
HI
IJ
JK
KL
LM
MN
NO
OP
PQ
QR
RS
ST
TU
UV
VW
WX
XY
YZ
ZA


Sample output:
Case #1: 2
Case #2: -1
Case #3: 0
Case #4: 3
Case #5: -1
Case #6: 8
Case #7: 100


Solution: As in Chapter 1, we'll consider each possible character \(x\) (`"A"` \(\le x \le\) `"Z"`) such that all characters in \(S\) are to be changed into \(x\). The only difference is in computing the minimum number of seconds it takes to change some character \(c\) into another character \(x\) (if it's possible at all).

If we imagine an unweighted graph with \(26\) nodes (one for each letter from `"A"` to `"Z"`), such that there's a directed edge from node \(A_i\) to node \(B_i\) for each type of replacement \(i\), then the minimum number of seconds required to change \(c\) into \(x\) is equal to the shortest length of any path from node \(c\) to node \(x\) (if any such path exists). 

We can precompute a \(26*26\) table of these shortest distances between all pairs of nodes by using the [Floyd–Warshall algorithm](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) or by performing a [BFS (breadth-first search)](https://en.wikipedia.org/wiki/Breadth-first_search) from each possible starting node, taking care to mark unreachable pairs of nodes as effectively having an infinite distance and being unusable in the final answer. For each character \(x\) and for each character \(c\) in \(S\), we can then look up the shortest distance from node \(c\) to node \(x\) in the table.

[See David Harmeyer's solution video here](https://youtu.be/p5yPTHNUTlc).


Code: #include <algorithm>
#include <iostream>
using namespace std;

const int INF = 1e6;

string S;
int K;
int dist[26][26];

int solve() {
  for (int i = 0; i < 26; i++) {
    for (int j = 0; j < 26; j++) {
      dist[i][j] = (i == j) ? 0 : INF;
    }
  }
  cin >> S >> K;
  for (int i = 0; i < K; i++) {
    char a, b;
    cin >> a >> b;
    dist[a - 'A'][b - 'A'] = 1;
  }
  for (int k = 0; k < 26; k++) {
    for (int i = 0; i < 26; i++) {
      for (int j = 0; j < 26; j++) {
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }
  int ans = INF;
  for (int i = 0; i < 26; i++) {
    int curr = 0;
    for (char c : S) {
      curr += dist[c - 'A'][i];
    }
    ans = min(ans, curr);
  }
  return ans == INF ? -1 : ans;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}