C |
Antonyms |
|
Input |
Standard Input |
|
Output |
Standard Output |
Little Rushel is preparing for his
English test. Part of the test includes matching pairs of words as antonyms or
synonyms. A pair of words are called synonyms of each other if both words mean
the same thing. For example, “big” and “large” are synonyms. A pair of words
are called antonyms of each other if each is the opposite of the other. For
example, “big” and “small” are antonyms.
For his test, Rushel needs to memorize a
huge list of words. This is really tedious and he would rather spend the time
learning to program. So, he comes up with a clever scheme. He notices that if
one word is a synonym of another, it is also the antonym of all words that are
antonyms of that word. This means that he needs only remember that the words
“big” and “large” are synonyms and that “big” and “small” are antonyms, and
from that he can infer that “large” and “small” are also antonyms. Thus he does
not need to memorize the relationship between all pairs of words, only enough
for him to be able to deduce the answer for the rest. Of course, not all words
are related (e.g. “big” and “cold”), but the examiner is a sensible person and
will not ask meaningless questions like that.
After a little more thought, Rushel
observed that for a set of words that are related, the following rules apply:
1. If A and B are synonyms and B and C are
synonyms, A and C are synonyms.
2. If A and B are synonyms and B and C are
antonyms, A and C are antonyms.
3. If A and B are antonyms and B and C are
synonyms, A and C are antonyms.
4. If A and B are antonyms and B and C are
antonyms, A and C are synonyms.
Unfortunately for Rushel, his friends
pointed out that the rules are too simple for a real human language like
English. For example, if fed the data that “ice” and “water” are antonyms, and
that “fire” and “water” are also antonyms, it would lead one to infer that
“ice” and “fire” are synonyms (by Rule 4), which is obviously wrong. Rushel
thinks that this is not really a good example (after all, it doesn't make a lot
of sense), but he is still concerned that there might be equally nonsensical
relationships in the words that he is learning. He has already prepared lists
of synonyms and antonyms to learn, he thinks it will be enough to just check if
any of them contain any contradictions.
A set of relationships is said to contain
a contradiction if some of the relationships imply or state that a certain pair
of words are synonyms while some of the other relationships imply or state that
the same pair are antonyms.
Please help Rushel, who is too young to
be allowed into this contest, by writing a program that takes as its input sets
of pairs of synonyms and antonyms and verifies that there are no contradictions
in them.
Input
The first line of the input will contain
a single integer T
all by itself, T ≤ 100.
T test cases follow.
Each test case starts with two numbers N and M (1 ≤ N, M ≤ 1000). N
lines follow, each containing a pair of words separated by one or more spaces.
Then another M
lines follow, also containing pairs of words separated by one or more spaces. Words
will be made up of lowercase English characters only ('a' to 'z'), and will
never be more than 20 characters long. The first set (the first N pairs) is the set of synonyms and the
second set (the latter M
pairs) is the set of antonyms.
Output
For each case output one line of the form
“Case
X: Y”, where X is the test case (starting from 1) and Y is either “YES” (if the test case contains no
contradictions) or “NO”
(if the input contains contradictions).
Sample Input |
Sample Output |
3 |
Case
1: YES |
Problemsetter: Muntasir Azam Khan, Special Thanks:
Sohel Hafiz