Under construction

Still being built. Things may change

Bad Horse (Small 1)

Interview

Time limit5sMemory limit512 MB

Summary
Decide for each test case whether members joined by troublesome pairs split into two groups with no pair in one group.
Level

Easy3 of 10

Topics
Graph, BFS
Solved
No attempts yet

Problem

Bad Horse, the leader of the Evil League of Evil, has a lot of problems to deal with. There have been far too many arguments and far too much backstabbing in the League lately, so Bad Horse has decided to split the League into two departments and keep the troublesome members apart. Being the Thoroughbred of Sin, Bad Horse is not about to spend his own time working out how to split the members. That is what he has you, his loyal henchman, for.

You are given a list of troublesome pairs of members. Decide whether the members named in that list can be put into two departments so that no department contains a troublesome pair. One of the two departments may stay empty.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a positive integer M on a line by itself, 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 ≤ T ≤ 100
  • Each member name consists of only letters and the underscore character.
  • Names are case sensitive.
  • No pair appears more than once in the same test case.
  • Each pair contains two distinct League members.
  • 1 ≤ M ≤ 10

Output

For each test case, output one line containing "Case #x: y", where x is the test case number starting from 1, and y is Yes if the members can be split into two departments with neither department containing a troublesome pair, and No otherwise.

Examples4

  1. 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

  2. Example 2

    Input
    1
1
A B
    Expected output
    Case #1: Yes

  3. Example 3

    Input
    2
4
N_a N_b
N_b N_c
N_c N_d
N_d N_a
5
P_a P_b
P_b P_c
P_c P_d
P_d P_e
P_e P_a
    Expected output
    Case #1: Yes
Case #2: No

  4. Example 4

    Input
    2
3
Bob bob
bob BOB
BOB Bob
2
Bob bob
bob BOB
    Expected output
    Case #1: No
Case #2: Yes