/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
あなたの運営する Web サービスには N 人のユーザがいます。
i 番目のユーザの現在のユーザ名は S_i ですが、T_i への変更を希望しています。
ここで、S_1,\ldots,S_N は相異なり、T_1,\ldots,T_N も相異なります。
ユーザ名を変更する順序を適切に定めることで、以下の条件を全て満たすように、全てのユーザのユーザ名を希望通り変更することができるか判定してください。
- ユーザ名の変更は 1 人ずつ行う
- どのユーザもユーザ名の変更は一度だけ行う
- ユーザ名の変更を試みる時点で他のユーザが使っているユーザ名に変更することはできない
制約
- 1 \leq N \leq 10^5
- S_i,T_i は英小文字からなる 1 文字以上 8 文字以下の文字列
- S_i \neq T_i
- S_i は相異なる
- T_i は相異なる
入力
入力は以下の形式で標準入力から与えられる。
N S_1 T_1 S_2 T_2 \vdots S_N T_N
出力
条件を全て満たすように全てのユーザのユーザ名を希望通り変更することができるとき Yes、できないとき No と出力せよ。
入力例 1
2 b m m d
出力例 1
Yes
1 番目のユーザの現在のユーザ名は b であり、m への変更を希望しています。
2 番目のユーザの現在のユーザ名は m であり、d への変更を希望しています。
まず、2 番目のユーザのユーザ名を m から d に変更し、
その後 1 番目のユーザのユーザ名を b から m に変更することで、条件を満たしながら変更することができます。
最初の時点では 2 番目のユーザのユーザ名が m なので、1 番目のユーザのユーザ名を同じ m に変更することはできません。
入力例 2
3 a b b c c a
出力例 2
No
1 番目のユーザの現在のユーザ名は a であり、b への変更を希望しています。
2 番目のユーザの現在のユーザ名は b であり、c への変更を希望しています。
3 番目のユーザの現在のユーザ名は c であり、a への変更を希望しています。
条件を満たしながらユーザ名の変更を行うことはできません。
入力例 3
5 aaa bbb yyy zzz ccc ddd xxx yyy bbb ccc
出力例 3
Yes
Score : 400 points
Problem Statement
You run a web service with N users.
The i-th user with a current handle S_i wants to change it to T_i.
Here, S_1,\ldots, and S_N are pairwise distinct, and so are T_1,\ldots, and T_N.
Determine if there is an appropriate order to change their handles to fulfill all of their requests subject to the following conditions:
- you change only one user's handle at a time;
- you change each user's handle only once;
- when changing the handle, the new handle should not be used by other users at that point.
Constraints
- 1 \leq N \leq 10^5
- S_i and T_i are strings of length between 1 and 8 (inclusive) consisting of lowercase English letters.
- S_i \neq T_i
- S_i are pairwise distinct.
- T_i are pairwise distinct.
Input
The input is given from Standard Input in the following format:
N S_1 T_1 S_2 T_2 \vdots S_N T_N
Output
Print Yes if they can change their handles to fulfill all of their requests subject to the conditions; print No otherwise.
Sample Input 1
2 b m m d
Sample Output 1
Yes
The 1-st user with a current handle b wants to change it to m.
The 2-nd user with a current handle m wants to change it to d.
First, you change the 2-nd user's handle from m to d;
then you change the 1-st user's handle from b to m. This way, you can achieve the objective.
Note that you cannot change the 1-st user's handle to m at first, because it is used by the 2-nd user at that point.
Sample Input 2
3 a b b c c a
Sample Output 2
No
The 1-st user with a current handle a wants to change it to b.
The 2-nd user with a current handle b wants to change it to c.
The 3-rd user with a current handle c wants to change it to a.
We cannot change their handles subject to the conditions.
Sample Input 3
5 aaa bbb yyy zzz ccc ddd xxx yyy bbb ccc
Sample Output 3
Yes