[ABC285D] Change Usernames

题面翻译

有 $N$ 个用户，每个用户有一个用户名 $S_i$ 现在每个用户都想改成另一个用户名 $T_i$，如果一个用户想要改的名字没有人正在用，那么这个用户可以改名。现在用户改名的顺序由你决定，请问是否所有用户都可以成功改名。

题目描述

あなたの運営する Web サービスには $N$ 人のユーザがいます。

$i$ 番目のユーザの現在のユーザ名は $S_i$ ですが、$T_i$ への変更を希望しています。 ここで、$S_1,\ldots,S_N$ は相異なり、$T_1,\ldots,T_N$ も相異なります。

ユーザ名を変更する順序を適切に定めることで、以下の条件を全て満たすように、全てのユーザのユーザ名を希望通り変更することができるか判定してください。

• ユーザ名の変更は $1$ 人ずつ行う
• どのユーザもユーザ名の変更は一度だけ行う
• ユーザ名の変更を試みる時点で他のユーザが使っているユーザ名に変更することはできない

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $S_1$ $T_1$ $S_2$ $T_2$ $\vdots$ $S_N$ $T_N$

输出格式

条件を全て満たすように全てのユーザのユーザ名を希望通り変更することができるとき Yes、できないとき No と出力せよ。

样例 #1

样例输入 #1

2
b m
m d

样例输出 #1

Yes

样例 #2

样例输入 #2

3
a b
b c
c a

样例输出 #2

No

样例 #3

样例输入 #3

5
aaa bbb
yyy zzz
ccc ddd
xxx yyy
bbb ccc

样例输出 #3

Yes

提示

制約

• $1\ \leq\ N\ \leq\ 10^5$
• $S_i,T_i$ は英小文字からなる $1$ 文字以上 $8$ 文字以下の文字列
• $S_i\ \neq\ T_i$
• $S_i$ は相異なる
• $T_i$ は相異なる

Sample Explanation 1

$1$ 番目のユーザの現在のユーザ名は b であり、m への変更を希望しています。 $2$ 番目のユーザの現在のユーザ名は m であり、d への変更を希望しています。 まず、$2$ 番目のユーザのユーザ名を m から d に変更し、 その後 $1$ 番目のユーザのユーザ名を b から m に変更することで、条件を満たしながら変更することができます。 最初の時点では $2$ 番目のユーザのユーザ名が m なので、$1$ 番目のユーザのユーザ名を同じ m に変更することはできません。

Sample Explanation 2

$1$ 番目のユーザの現在のユーザ名は a であり、b への変更を希望しています。 $2$ 番目のユーザの現在のユーザ名は b であり、c への変更を希望しています。 $3$ 番目のユーザの現在のユーザ名は c であり、a への変更を希望しています。 条件を満たしながらユーザ名の変更を行うことはできません。