← 返回题目列表

AtCoder · abc285_d

G. 更改用户名

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

您运行一个 Web 服务 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-st 具有当前句柄的用户 b 想将其更改为 m.
的 2- 具有当前句柄的第一个用户 m 想将其更改为 d.

首先,您更改 2-nd 用户句柄来自 m to d; 然后你改变 1-st 用户句柄来自 b to m。 这样,您就可以达到目的。

请注意,您无法更改 1-st 用户的句柄 m 首先,因为它被使用 2- 此时的第一个用户。


示例输入 2

3
a b
b c
c a

示例输出 2

No

的 1-st 具有当前句柄的用户 a 想将其更改为 b.
的 2- 具有当前句柄的第一个用户 b 想将其更改为 c.
的 3-rd 用户具有当前句柄 c 想将其更改为 a.

根据条件,我们无法更改其句柄。


示例输入 3

5
aaa bbb
yyy zzz
ccc ddd
xxx yyy
bbb ccc

示例输出 3

Yes