Bad Horse (Small2)

Interview

Time limit5sMemory limit512 MB

Summary

Decide whether members linked by troublesome pairs split into two groups with no pair inside one group.

Level: Easy3 of 10
Topics: Graph, BFS
Solved: No attempts yet

Problem

Bad Horse leads the Evil League of Evil, and he has a lot of problems to deal with. Arguments and backstabbing inside the League have gotten out of hand, so Bad Horse decided to split the League into two departments and keep the troublesome members apart. Being the Thoroughbred of Sin, he is not about to spend his own valuable time working out how to split the members. That is what he has you, his loyal henchman, for.

You are given the list of troublesome pairs. Decide whether every member can be assigned to one of the two departments so that no department contains a troublesome pair. Only the members whose names appear in the input need an assignment.

Input

The first line contains the number of test cases $T$ . $T$ test cases follow.

Each test case starts with a line holding a positive integer $M$ , the number of troublesome pairs of League members. The next $M$ lines each contain a pair of names separated by a single space.

Limits

$1 \le T \le 100$
Each member name consists of letters and the underscore character only.
Names are case-sensitive.
No pair appears more than once in the same test case.
The two members of a pair are always different.
$1 \le M \le 100$

Output

For each test case, print one line of the form Case #x: y, where $x$ is the case number starting from 1, and $y$ is Yes if the members mentioned in the input can be split into two groups with neither group containing a troublesome pair, and No otherwise.

Examples4

Example 1

Input

2
1
Dead_Bowie Fake_Thomas_Jefferson
3
Dead_Bowie Fake_Thomas_Jefferson
Fake_Thomas_Jefferson Fury_Leika
Fury_Leika Dead_Bowie

Expected output

Case #1: Yes
Case #2: No

Example 2
Input
```
1
1
A B
```
Expected output
```
Case #1: Yes
```

Example 3

Input

2
4
a b
b c
c d
d a
5
p q
q r
r s
s t
t p

Expected output

Case #1: Yes
Case #2: No

Example 4

Input

2
5
xa xb
xb xc
xc xa
ya yb
yb yc
3
u v
v w
w x

Expected output

Case #1: No
Case #2: Yes