To decide whether the string ~S~ could map to ~T~, we first have to realize what this is telling us: for each valid ~i~, ~S_i~ maps to ~T_i~. We can immediately answer NO if any of the following conditions is satisfied:

• Two letters map to the same letter.
• The same letter maps to two different letters.
• A letter maps to a letter other than one of the two possibilities specified in the input.

However, as the second sample case shows, this is not sufficient to determine if the mapping is valid. The following algorithm works:

1. Find a letter which has not yet been assigned, but for which one of the two possibilities for that letter is taken. If there is no such letter, go to step 4.
2. Assign to that letter the possibility which is not taken.
3. Go to step 1.
4. Check the conditions mentioned above and answer YES if none of them are satisfied.

The proof of correctness is left as an exercise to the reader. (That is, I have no proof, but it gets the same answer as my bipartite matching solution for every test case I can create.) (Hint from d: Consider a graph where the nodes are the first ~A~ English letters, and the edges are ~(a_i, b_i)~. This graph is initially a pseudoforest. What happens to this graph during the algorithm?)

Complexity: ~\mathcal{O}(NA^2)~