[ official answer by CMI]
Let R be the set of states that can be reached by a path from the initial state in A and let S be the set of states from which there is a path to one of the final states in A.
For each pair of states (r, s) ∈ R × S, Ar,s is obtained from A by keeping the set of states and set of transitions unchanged, but making r the unique intial state and s the unique final state.
If u ∈ L(Ar,s), then there must be a word xuy ∈ L(A), where x labels the path from the initial state to r (r ∈ R is reachable from the initial state), u labels the path from r to s, and y labels the path from s to some final state of A (s ∈ S, so such a path must exist.)
Hence, output “Yes” if u ∈ L(Ar,s) for some (r, s) ∈ R × S, and “No” otherwise.