更改用户名

题目描述

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

第 1 个用户当前的用户名是 b,想改成 m。

第 2 个用户当前的用户名是 m,想改成 d。

首先把第 2 个用户的用户名从 m 改成 d,然后把第 1 个用户的用户名从 b 改成 m。这样就能达成目标。

注意,不能一开始就把第 1 个用户的用户名改成 m,因为那一刻 m 正被第 2 个用户使用。

3
a b
b c
c a

No

第 1 个用户当前的用户名是 a,想改成 b。

第 2 个用户当前的用户名是 b,想改成 c。

第 3 个用户当前的用户名是 c,想改成 a。

我们无法在满足条件的情况下完成改名。

5
aaa bbb
yyy zzz
ccc ddd
xxx yyy
bbb ccc

Yes

数据范围

• $1 \le N \le 10^5$
• $S_i$、$T_i$ 是由小写英文字母组成的长度在 $1$ 到 $8$ 之间(含两端)的字符串。
• $S_i \neq T_i$
• $S_i$ 两两不同。
• $T_i$ 两两不同。