Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2611

Time Limit: 2 Seconds      Memory Limit: 65536 KB      Special Judge

Association of Challenge Masters (ACM) sponsored by International Battle Merchandisers (IBM) is planning to create a series of new quest games. Brotherhood of Tired Virtual Adventurers (BoTVA) has stolen the scripts of the quests and now is planning to publish the solution guide for all the games. In all quests the adventures take part in some building that has several rooms. Rooms are connected to each other by the doors. The doors are opened using the keys. Also there are characters, objects and items in the game. Keys are considered to be items.

The player in the quest can talk to any character. After he does, the character names several items that he needs to give the player some other items. After the player bring the requested items to him, he get the items promised. Some items can be found on the floor. Also the player may use items on objects. After doing so, he may get some other items.

Given the description of the quest world, create the solution guide for it - the sequence of actions one must do to complete the quest - save the princess.


The input contains multiple test cases. The first line of the input is a single integer T (1 <= T <= 30) which is the number of test cases. T test cases follow, each preceded by a single blank line.

In each case, the first line contains n - the number of the rooms in the game. Next n lines contain the names of the rooms. Next line contains m - the number of the doors. Next m lines describe doors - each line contains the numbers of the rooms connected by the door and the name of the key to open the door.

The descriptions of the contents of the rooms follow. Each description starts with three integers: c - the number of characters in the room and o - the number of objects in the room and i - the number of items on the floor of the room.

Next lines contain descrpitons of the characters. Each description consists of three lines. The first line contains the name of the character. Next line contains one or more item names - the items the character wants the player to bring to him. Last line also contains one or more item names - the names of the items the character would give to the player after he brings him the requested items. Item names are separated by commas. The descriptions of the objects in the same format follow. Note that the difference between objects and characters is that after the player gives some item to the character, it no longer belongs to him, while after using some item on object he keeps the item. Also one cannot talk to objects. Last i lines in the descrpiton of the room contain the names of the items on its floor.

Two last lines of each case contain the name of the room the player starts the game in, and the name of the room where the princess is locked.

All names consist only of letters of English alphabet, digits and spaces. You must ignore leading and trailing spaces in all names. All names are case sensitive. All names are at most 100 characters long. All names are different. The number of rooms is at least two and does not exceed eight. There is at most one door between any two rooms. All doors are two-way. The total number of characters, objects and items in the game does not exceed 200. You always start in the room other then the room where the princess is. No item is requested by more than one character, no item is simultaneously requested by some character and needed by some object. No item is provided by more than one character or object, or both, no item is both on the floor of some room and provided by some character or object. No key opens more than one door, no key is required by any object or character.


Output the sequence of the actions.

Remember that the player can: talk to character, give items to character (after talking to him), take items from character (immediately after giving him items he requests), use items on objects, take items from objects (immediately after using items needed on it), pick items from the floor, open the doors using the keys, walk from room to room (after opening the door that connects them), save the princess (if the player is in the room where the princess is).

Adhere to the format of the sample output. For each test case, print one action on a line. The player must always give all requested items to the character, use all needed items on the object, and take items from the character or the object in one action.

If it is impossible to win the game, output "dead princess" on a single line.

Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case.

Sample Input


white room
black room
blue room
green room
1 3 crystal key
1 4 esmerald key
2 3 strange key
0 0 2
crystal key
0 0 0
2 1 0
Wild Joe
rat, red pepper, coin
strange key
Dead man
orange juice
red pepper, esmerald key
orange juice
0 1 1
white room
black room

white room
black room
0 0 0
0 0 0
white room
black room

Sample Output

pick crystal key
pick oranges
open door to blue room
go to blue room
use oranges on squeezer
take orange juice from squeezer
talk to Dead man
give orange juice to Dead man
take red pepper and esmerald key from Dead man
go to white room
open door to green room
go to green room
pick rat
use oranges on monkey
take coin from monkey
go to white room
go to blue room
talk to Wild Joe
give red pepper, coin and rat to Wild Joe
take strange key from Wild Joe
open door to black room
go to black room
save princess

dead princess

Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #7
Submit    Status