Back to Category
d066: [2005] G - Treasure Island
Keyword: NCPC 2005

Difficulity: N/A | Test Data Sets: 1 (Hidden) | Judging: Traditional Judge
Accepted : 0 Times | Submit :100 Times | Clicks : 988
Accepted : 0 Users | Submit : 5 Users | Accepted rate : 0%
Time Limit :1000 ms | Memory Limit : 64000 KBytes
Update : 2009-09-13 15:56


A theme park called “Treasure Island” is newly opened. In the theme park, there are islands connected with bridges, where bridges are directed and one-way only. One major game of the theme park is a competition for collecting hidden treasures. A group of players may begin their search from an entrance island. In each island, some keys are placed in an obvious place. These keys can open a particular treasure if players can find it.

Image the keys and treasures have unlimited supply. Once a treasure is taken by some player, a new treasure will be supplied automatically. To prevent malicious players from collecting all the visible artifacts as their potential treasures, image a treasure is not removable if a player does not have correct keys at his/her hand to open the locks of treasures. In this theme park, players
can choose different routes (even loops) to collect their treasures. Once they collect all the needed treasures, they can leave from an exit island. You are the staff of the park. Everyday, you need to deploy keys and treasures. The deployment is different from day to day. In order to make the game easy and fair, a basic rule of key-treasure deployment is:

For any path (no matter how players choose their routes), a key should always appear first (shown to players) before its treasure’s hidden island.

So, if a treasure X is hidden on some island Y, before a player visits island Y, a key for treasure X should be already shown to the player.



Let a key of treasure X be KeyX. In figure 1, a deployment of treasures and keys is illustrated. In this deployment, treasure A is placed in island 4 and treasure B is placed in island 2. Three keys are placed in island 1,3, and 4 respectively.

In this sample deployment, treasure B satisfies the rule. Players choose any route to island 2 will always get the KeyB first. However, treasure A does not satisfy the rule – if a player chooses the route 1->2->4, he may see the treasure A without obtaining a KeyA first.

Please write a program for the staffs of theme park. Given a deployment, please find out the treasures whose key-treasure deployments violate the basic rule.


The first line of the input data is a number N. N is the number of test cases. Each test case begins with numbers M and D. M is the number of islands. D is the number of deployment lines. By default, islands are indexed from 1 to M. Island 1 is the entrance island and island M is the exit island. Next, D lines of deployments are listed. Each deployment line begins with the island’s index and then followed by keys or treasures. If a treasure X is deployed in the island, a string ”X” is added in the deployment line, where X is ”A”-”Z”. If a KeyX is placed in the island, a string ”KX” appears in the deployment line. Items in a deployment line are separated by spaces. A ”$” indicates there are no more items in the deployment line. NOTE: If an island is not listed in the deployment lines, it does not have treasures or keys deployed. NOTE: The number of directed bridges from an island to another island is not limited to

Following the deployment lines are information of directed bridges. Bridge information begins with a number B. B is the number of directed bridges. Next, B lines of bridges are followed. Each bridge is denoted by the index of source island and destination island.

Technical Specification

  1. N (1 ≤ N ≤ 20).
  2. M (1 ≤ M ≤ 1000).
  3. B (1 ≤ B ≤ 10000).


For each test case, output the treasures (in capital letters) that violate the rule in one line with alphabetical order such as: ACDFG (without spaces)

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
4 4
1 KB $
2 B $
3 KA $
4 A KB $
1 2
1 3
2 4
3 4
4 2

Sample Output :


Hint :

Author :

NCPC 2005

  Solve it!   Status Forum


Program running time may be affected by various factors. Check server system environment information here