/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
人 1, 人 2, \dots 人 N の 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 を出力してください。
制約
- 2 \leq N \leq 100
- N は整数である。
- s_i,t_i は英小文字からなる 1 文字以上 10 文字以下の文字列である。
入力
入力は以下の形式で標準入力から与えられる。
N s_1 t_1 s_2 t_2 \vdots s_N t_N
出力
N 人すべてにあだ名をつけることが可能ならば Yes を、そうでないならば No を出力せよ。
入力例 1
3 tanaka taro tanaka jiro suzuki hanako
出力例 1
Yes
a_1 = taro, a_2 = jiro, a_3 = hanako とすれば、これは問題文にあるあだ名の条件を満たしています。(a_3 は suzuki でもよいです。)
ここで、a_1 = tanaka とはできないことに注意してください。なぜならば 人 2 の姓 s_2 もまた tanaka であるため、あだ名の条件の 2 つ目を満たさなくなるからです。
入力例 2
3 aaa bbb xxx aaa bbb yyy
出力例 2
No
問題文の条件を満たすあだ名のつけ方は存在しません。
入力例 3
2 tanaka taro tanaka taro
出力例 3
No
同姓同名である人の組が存在する場合もあります。
入力例 4
3 takahashi chokudai aoki kensho snu ke
出力例 4
Yes
a_1 = chokudai, a_2 = kensho, a_3 = ke とすればよいです。
Score : 200 points
Problem Statement
There are N people numbered Person 1, Person 2, \dots, and Person N. Person i has a family name s_i and a given name t_i.
Consider giving a nickname to each of the N people. Person i's nickname a_i should satisfy all the conditions below.
- a_i coincides with Person i's family name or given name. In other words, a_i = s_i and/or a_i = t_i holds.
- a_i does not coincide with the family name and the given name of any other person. In other words, for all integer j such that 1 \leq j \leq N and i \neq j, it holds that a_i \neq s_j and a_i \neq t_j.
Is it possible to give nicknames to all the N people? If it is possible, print Yes; otherwise, print No.
Constraints
- 2 \leq N \leq 100
- N is an integer.
- s_i and t_i are strings of lengths between 1 and 10 (inclusive) consisting of lowercase English alphabets.
Input
Input is given from Standard Input in the following format:
N s_1 t_1 s_2 t_2 \vdots s_N t_N
Output
If it is possible to give nicknames to all the N people, print Yes; otherwise, print No.
Sample Input 1
3 tanaka taro tanaka jiro suzuki hanako
Sample Output 1
Yes
The following assignment satisfies the conditions of nicknames described in the Problem Statement: a_1 = taro, a_2 = jiro, a_3 = hanako. (a_3 may be suzuki, too.)
However, note that we cannot let a_1 = tanaka, which violates the second condition of nicknames, since Person 2's family name s_2 is tanaka too.
Sample Input 2
3 aaa bbb xxx aaa bbb yyy
Sample Output 2
No
There is no way to give nicknames satisfying the conditions in the Problem Statement.
Sample Input 3
2 tanaka taro tanaka taro
Sample Output 3
No
There may be a pair of people with the same family name and the same given name.
Sample Input 4
3 takahashi chokudai aoki kensho snu ke
Sample Output 4
Yes
We can let a_1 = chokudai, a_2 = kensho, and a_3 = ke.