AT_abc285_d [ABC285D] Change Usernames

题目描述

你的 Web 服务有 $N$ 个用户。

第 $i$ 个用户当前的用户名为 $S_i$，但希望更改为 $T_i$。
这里，$S_1,\ldots,S_N$ 互不相同，$T_1,\ldots,T_N$ 也互不相同。

请判断是否可以通过适当安排用户名更改的顺序，使得所有用户都能如愿更改用户名，并且满足以下所有条件：

• 用户名的更改一次只进行一个用户。
• 每个用户只能更改一次用户名。
• 在尝试更改用户名时，不能更改为其他用户正在使用的用户名。

输入格式

输入按以下格式从标准输入读入。

$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$ 互不相同。

样例解释 1

第 $1$ 个用户当前用户名为 b，希望更改为 m。第 $2$ 个用户当前用户名为 m，希望更改为 d。
可以先将第 $2$ 个用户的用户名从 m 改为 d，然后再将第 $1$ 个用户的用户名从 b 改为 m，这样就能满足所有条件。
一开始第 $2$ 个用户的用户名是 m，因此不能直接将第 $1$ 个用户的用户名改为同样的 m。

样例解释 2

第 $1$ 个用户当前用户名为 a，希望更改为 b。第 $2$ 个用户当前用户名为 b，希望更改为 c。第 $3$ 个用户当前用户名为 c，希望更改为 a。
无法在满足条件的情况下完成所有用户名的更改。

由 ChatGPT 4.1 翻译