AT_abc247_b [ABC247B] Unique Nicknames

题目描述

有 $N$ 个人，分别为人 $1$、人 $2$、$\dots$、人 $N$。第 $i$ 个人的姓为 $s_i$，名为 $t_i$。

现在要为这 $N$ 个人每人取一个昵称。第 $i$ 个人的昵称 $a_i$ 需要满足以下条件：

• $a_i$ 必须等于第 $i$ 个人的姓或名。换句话说，$a_i = s_i$ 或 $a_i = t_i$ 至少有一个成立。
• $a_i$ 不能等于除自己以外任何人的姓或名。也就是说，对于所有满足 $1 \leq j \leq N,\, i \neq j$ 的整数 $j$，都有 $a_i \neq s_j$ 且 $a_i \neq t_j$。

请判断是否可以为所有 $N$ 个人都取出满足条件的昵称。如果可以，输出 Yes，否则输出 No。

输入格式

输入以如下格式从标准输入给出。

$N$
$s_1$ $t_1$
$s_2$ $t_2$
$\vdots$
$s_N$ $t_N$

输出格式

如果可以为所有 $N$ 个人都取出满足条件的昵称，输出 Yes；否则输出 No。

输入输出样例 #1

输入 #1

3
tanaka taro
tanaka jiro
suzuki hanako

输出 #1

Yes

输入输出样例 #2

输入 #2

3
aaa bbb
xxx aaa
bbb yyy

输出 #2

No

输入输出样例 #3

输入 #3

2
tanaka taro
tanaka taro

输出 #3

No

输入输出样例 #4

输入 #4

3
takahashi chokudai
aoki kensho
snu ke

输出 #4

Yes

说明/提示

限制条件

• $2 \leq N \leq 100$
• $N$ 是整数。
• $s_i, t_i$ 是由小写英文字母组成的字符串，长度在 $1$ 到 $10$ 之间。

样例解释 1

取 $a_1 = \texttt{taro}$，$a_2 = \texttt{jiro}$，$a_3 = \texttt{hanako}$，这样就满足了题目中昵称的条件。（$a_3$ 取 $\texttt{suzuki}$ 也可以。）注意，$a_1$ 不能取 $\texttt{tanaka}$，因为第 $2$ 个人的姓 $s_2$ 也是 $\texttt{tanaka}$，这样就不满足昵称的第二个条件。

样例解释 2

不存在满足题目条件的昵称的取法。

样例解释 3

也可能存在同姓同名的人。

样例解释 4

取 $a_1 = \texttt{chokudai}$，$a_2 = \texttt{kensho}$，$a_3 = \texttt{ke}$ 即可。

由 ChatGPT 4.1 翻译