Coke or Chocolate Milk

Time limit1sMemory limit128 MB

Summary
Assign each person one of two drinks so that desire, hatred, sameness, difference, and conditional requests all hold, printing the alphabetically earliest Coke-preferring satisfying assignment or reporting failure.
Level

Medium7 of 10

Topics
Graph, DFS, Implementation, Greedy
Solved
No attempts yet

Problem

Anybody who has been to a child's birthday party has seen the following scene:

Parent: OK kids, what do you want to drink, Coke or chocolate milk?

Jamie: Coke.

John: I hate Coke.

Mary: I want what John is having.

Barry: Ick! Then I don't want it if she's going to have it.

… etc.

This is a big party. 1000 people have been invited and nearly that many may show up. Can you make everybody happy?

Input

The input may contain several test cases. The first line of each test case is an integer NN, the number of requests that must be satisfied. The next NN lines each contain one request, in one of the following five formats:

<person> wants <drink>
<person> hates <drink>
<person> wants same as <person>
<person> wants different from <person>
<person> wants <drink> if <person> gets <drink>

<person> is the name of a person — up to 20 lower-case letters. <drink> is either Coke or chocolate milk.

Each request means:

  • <person> wants <drink>: that person must get that drink.
  • <person> hates <drink>: that person must not get that drink (so they get the other one).
  • A wants same as B: A and B must get the same drink.
  • A wants different from B: A and B must get different drinks.
  • A wants X if B gets Y: if B gets Y, then A must get X.

The input ends with a line whose value of NN is 0.

Output

For each test case, if everybody can be made happy, print one line per person, in alphabetical order of their names, in the format:

<person> gets <drink>

If there is more than one way to make everybody happy, fill the glasses in alphabetical order and pour Coke whenever there is a choice (it is cheaper) — that is, print the assignment uniquely determined by this rule.

If it is not possible to make everybody happy, print the single line:

Everybody gets water

Separate the outputs of two consecutive test cases with a single blank line.

Examples4

  1. Example 1

    Input
    4
jamie wants Coke
john hates Coke
mary wants same as john
barry wants different from mary
0
    Expected output
    barry gets Coke
jamie gets Coke
john gets chocolate milk
mary gets chocolate milk

  2. Example 2

    Input
    1
alice wants different from alice
0
    Expected output
    Everybody gets water

  3. Example 3

    Input
    1
bob wants chocolate milk
0
    Expected output
    bob gets chocolate milk

  4. Example 4

    Input
    1
a wants same as b
0
    Expected output
    a gets Coke
b gets Coke