Change Usernames

题目描述

你运营着一个有 $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$。

2
b m
m d

Yes

3
a b
b c
c a

No

5
aaa bbb
yyy zzz
ccc ddd
xxx yyy
bbb ccc

Yes

提示

$1 \leq N \leq 10^5$ $S_i$ 和 $T_i$ 是长度在 $1$ 到 $8$（含）之间、由小写英文字母组成的字符串。 $S_i \neq T_i$ $S_i$ 两两互不相同。 $T_i$ 两两互不相同。第 $1$ 个用户当前的用户名为 $b$，希望改为 $m$。
第 $2$ 个用户当前的用户名为 $m$，希望改为 $d$。 首先，将第 $2$ 个用户的用户名从 $m$ 改为 $d$； 然后将第 $1$ 个用户的用户名从 $b$ 改为 $m$。这样就可以达到目标。 注意不能先把第 $1$ 个用户的用户名改为 $m$，因为此时它被第 $2$ 个用户使用着。
第 $1$ 个用户当前的用户名为 $a$，希望改为 $b$.
第 $2$ 个用户当前的用户名为 $b$，希望改为 $c$.
第 $3$ 个用户当前的用户名为 $c$，希望改为 $a$。 在满足条件的情况下，无法更改他们的用户名。

标签: AtCoder|abc285D

来源

AtCoder|abc285D