9193: ABC285 —— D - Change Usernames
[Creator : ]
Description
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.
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.
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$
```
```
$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.
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.
- $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.
Sample 1 Input
2
b m
m d
Sample 1 Output
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.
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 ob
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 2 Input
3
a b
b c
c a
Sample 2 Output
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.
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 3 Input
5
aaa bbb
yyy zzz
ccc ddd
xxx yyy
bbb ccc
Sample 3 Output
Yes