Interview
You have been called to an interview at Jifatsum, a company you’ve never heard of and who supposedly have a thousand employees all packed into what looks like garage converted into a makeshift office. You go through several rounds of interviews, with each round consisting of two interviewers. You can have the same interviewer appear in more than one round. The company says that they will have N people interviewing you. But many of the interviewers look suspiciously alike, some have false mustaches that fall off, while others just seem like the same person now just wearing glasses like Superman. The only way to be sure that two interviewers are not the same is to have seen them together in the same room.
The company says they have N interviewers, although you may or may not get to see all of them in the M interviews you have. You have your suspicions though, you think the company has at most K interviewers.
Given that you are told that the company has N interviewers, you go through M sets of interviews and suspect there are actually at most K interviewers, can you check if your suspicions are valid?
For example, if you've seen person A and B in the same room, you can be sure that they are indeed not the same person. If you see person A and C in the same room, then again A and C cannot be the same person. So you have a person A who must be distinct from B or C, but you have not seen B and C in the same room, so they might be the same person. In this scenario, they might actually have two people, A and another person pretending to be both B and C.
If, however, you have seen A and B, A and C, and B and C in the same room, every person has been in the same room with the two other people. So they must all be distinct and there have to be three people.
Input
The first line of input is an integer T, the number of test cases. Then, T test cases follow.
Each test case starts with three lines containing N, M, and K respectively.
M lines follow, each containing the pair of interviewers X and Y, which means person X and person Y were with you in the same room at the same time.
Output
For each test case print a single line of the form:
“Case <case number>: Yes” if your suspicion is correct and there are indeed at most K people there or “Case <case number>: No” if there must be more than K people there.
Limits:
1 ≤ T ≤ 50
1 ≤ N ≤ 16
0 ≤ M ≤ 120
1 ≤ K ≤ 16
0 ≤ X,Y < N
Sample
| Input | Output |
|---|---|
2 3 2 2 0 1 1 2 3 3 2 0 1 1 2 0 2 | Case 1: Yes Case 2: No |
The first sample cases are from the two examples in the statement.
In the first case, you have the company claiming to have three interviewers but you suspect two. You have two interviews and see person 0 and 1, and person 0 and 2 in the same room. This can be done with two people since person 0 has to be distinct, but person 1 and 2 can be the same, so your suspicion is confirmed and your solution should print "Yes".
In the second example, you have the same setup as the previous sample except that now you have also seen person 0 and 2 in the same room. This cannot be done with only two interviewers, so your program should output "No".
