102853: [AtCoder]ABC285 D - Change Usernames
Description
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
Input
题意翻译
有 $N$ 个用户，每个用户有一个用户名 $S_i$ 现在每个用户都想改成另**一个**用户名 $T_i$，如果一个用户想要改的名字没有人**正在**用，那么这个用户可以改名。现在用户改名的顺序由你决定，请问是否所有用户都可以成功改名。Output
问题描述
您运行一个有N个用户的服务。
第i个用户当前的别名是$S_i$，想要将其更改为$T_i$。
其中，$S_1,\ldots$和$S_N$是两两不同的，$T_1,\ldots$和$T_N$也是两两不同的。
确定是否可以按照以下条件更改他们的别名以满足所有请求：
- 一次只更改一个用户的别名；
- 每个用户的别名只能更改一次；
- 更改别名时，新别名在那一刻不应被其他用户使用。
限制条件
- $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。这样，您就可以实现目标。
注意，您不能首先将第1个用户的别名更改为m，因为它在那一刻被第2个用户使用。
样例输入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