Old pals P93727


pdf   zip


Some pals from the good old days at the university plan to meet again and have a party. To decide how the party will be, they have written a list of categories (for food, music, etc), each one with several possibilities. All the categories are mutually independent, that is, what is chosen for a category does not affect what can be chosen for another one.

Consider the first example in the sample input. Depending on the cooker, they can have as main dish either fast food or vegetarian food. Depending on who chooses the music, it can be classic, alternative or heavy. One of the friends has two specialties: making milk shakes and baking croissants, but he has only time for one of them. Finally, they can even enjoy a sauna or a swimming pool, depending on whose house the party takes place.


They are too fastidious, but they finally agree to require two conditions, and to go to the party if at least one of them is satisfied. Following the example, Mr. Morito likes milk shakes and saunas, Mr. Vinyes prefers alternative music and croissants, Mr. Masdeu likes heavy music and vegetarian food, while Mr. Maltines enjoys fast food and saunas. One possible solution is eating vegetarian food and croissants in a house with sauna, listening to any kind of music (or to no music at all).

Let us formalize the problem. There is a list of categories and a list of friends. Every category has several possibilities. Every friend asks for two different conditions chosen among the possibilities of the categories. Your task is to decide if there is a way to pick (at most) one possibility per category so that at least one condition per friend is satisfied.


Input begins with the number of cases. Every case has two parts: the first for the categories, the second for the conditions. The categories’ part begins with a number c ≥ 1 followed by c lines, each one with at least two possibilities (strings). The conditions’ part begins with a number 1 ≤ f ≤ 1000 followed by f lines, each one with three strings: the surname’s friend and two different conditions present in the categories part.

Every string has at most 20 letters and underscores. The strings in the categories’ part of the same case are all different. For each case, the total number of possibilities of all the categories is at most 200.


For every case, print the case number, followed by the right answer “yes” or “no”.

Public test cases
  • Input

    fast_food vegetarian_food
    classic_music alternative_music heavy_music
    milk_shakes croissants
    sauna swimming_pool
    Morito milk_shakes sauna
    Vinyes alternative_music croissants
    Masdeu heavy_music vegetarian_food
    Maltines fast_food sauna
    aa bb cc
    xx yy zz
    f aa xx
    g bb yy
    h cc zz
    a b c d e
    Lonesome b d


    Case #1: yes
    Case #2: no
    Case #3: yes
  • Information
    Salvador Roura
    Official solutions
    User solutions