ヒント

ユーザ名の変更処理のうちのいくつかの間には、「あるユーザのユーザ名を変更してからでないと、別のユーザのユーザ名を変更できない」という依存関係があります。これらの依存関係をグラフにし、どの処理から行うべきかを考えてみましょう。

解法

文字列を頂点とし、\(S_i\) から \(T_i\) へ有向辺を張ったグラフを考えます。このグラフにサイクルがあるとき、サイクルに属する辺に対応するユーザ名の変更を行うことができません。したがって答えは No です。逆にそうでないとき、「出次数が \(0\) である頂点へ向かう辺に対応するユーザ名の変更を行い、その頂点を削除する」という操作を繰り返すことにより、すべてのユーザのユーザ名を変更することができるため、答えは Yes となります。

以上より、グラフにサイクルが存在するかを判定できればよく、DFS/BFSやUnion-Findなどにより判定できます。