2274: Unique Nicknames
[Creator : ]
Description
题意：
给出一个整数n和n个人的姓和名
问能否给每个人都起一个昵称，给一个人起昵称，要符合两个条件：
1. 每个人的昵称必须是这个人的姓或者名；
2. 每个人的昵称，不能与任何其他人的姓或名同名。
如果能按上述要求，给每个人起昵称，输出Yes，否则输出No
Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 200200 points
Consider giving a nickname to each of the NN people. Person ii's nickname a_iai should satisfy all the conditions below.
Problem Statement
There are NN people numbered Person 11, Person 22, \dots…, and Person NN. Person ii has a family name s_isi and a given name t_iti.Consider giving a nickname to each of the NN people. Person ii's nickname a_iai should satisfy all the conditions below.
- a_iai coincides with Person ii's family name or given name. In other words, a_i = s_iai=si and/or a_i = t_iai=ti holds.
- a_iai does not coincide with the family name and the given name of any other person. In other words, for all integer jj such that 1 \leq j \leq N1≤j≤N and i \neq ji=j, it holds that a_i \neq s_jai=sj and a_i \neq t_jai=tj.
Constraints
- 2 \leq N \leq 1002≤N≤100
- NN is an integer.
- s_isi and t_iti are strings of lengths between 11 and 1010 (inclusive) consisting of lowercase English alphabets.
Input
Input is given from Standard Input in the following format:NNs_1s1t_1t1s_2s2t_2t2\vdots⋮s_NsNt_NtN
Output
If it is possible to give nicknames to all the NN people, print Yes; otherwise, print No.Sample Input Copy
3
tanaka taro
tanaka jiro
suzuki hanako
Sample Output Copy
Yes
HINT
The following assignment satisfies the conditions of nicknames described in the Problem Statement: a_1 =a1= taro, a_2 =a2= jiro, a_3 =a3= hanako. (a_3a3 may be suzuki, too.)
However, note that we cannot let a_1 =a1= tanaka, which violates the second condition of nicknames, since Person 22's family name s_2s2 is tanaka too.
However, note that we cannot let a_1 =a1= tanaka, which violates the second condition of nicknames, since Person 22's family name s_2s2 is tanaka too.