ZOJ Problem Set - 3526
As the only Oni (a kind of fabulous creature with incredible strength and power) living on the surface of Gensokyo, Ibuki Suika has an interest in gathering Humans and Youkai in Gensokyo and holding party every day.
Today Suika has asked several friends to participate in a weekend party, which will be held at Hakurei Shrine as usual. Though Gensokyo was isolated from the outside world, everyone here is still a fan of ACG (Anime, Comic and Game). Of course, some people may only like parts of ACG. For example, Reimu likes Anime and Game, Marisa only likes Comic but Kaguya likes all of them.
In order to make everyone enjoy the party, Suika decide to arrange them into a circle so that everyone can have at least one common interest with both left and right hand side, which means one has at least a common interest with left AND has at least a common interest with right. By the way, Suika knows all her friends' interest. Please find out if she can get an arrangement of seats that satisfies the constraint described above.
There are multiple test cases. For each test case:
The first line contains an integer N (1 <= N <= 64) indicates the number of girls in Gensokyo. Then followed by N lines, each line contains two strings Ai and Bi (each contains only alphanumeric characters). Ai represents the name of the i-th girl and the length of it will not exceed 10. Bi is a non-empty subset of "ACG".
For each test case, output "Yes" if there exists at least one arrangement of seats, otherwise output "No".
1 Reimu AG 2 Reimu AG Marisa C 3 Reimu AG Marisa C Kaguya GAC
Yes No No
Author: YU, Xiaoyao