AIOC Banner

Problem: Carmen Sanfrancisco

Want to try solving this problem? You can submit your code online if you log in or register.

Carmen Sanfrancisco

Input File: wherein.txt
Output File: whereout.txt
Time Limit: 1 second

After a mysterious ten year absence, notorious international landmark thief Carmen Sanfrancisco is back and burgling like never before. On Wednesday 2 September, under the cover of night, the villainess stole the Eiffel Tower. But while Carmen Sanfrancisco can run, she can't hide.

The ACME Detective Agency has requested your services as an elite detective in tracking down the stolen Eiffel Tower. You have fellow agents scattered throughout the world--lurking in bus companies, train companies, taxi ranks and airlines. While your agents are numerous they are somewhat ineffective, incapable of ever actually determining where in the world Carmen is at any point in time. Instead, they can merely tell you which mode of transport (such as bus, train, taxi and so on) Carmen uses each time she moves between two cities.

Carmen is only able to move between two cities if there is a transport link between them. Transport links are always bi-directional; for instance, if Carmen can catch a plane from Paris to Prague, she could also catch a plane back from Prague to Paris. Additionally, a pair of cities may have more than one mode of transport connecting them; Prague and Paris could be connected by both plane and train, for example.

You have obtained a map of all the cities in which Carmen Sanfrancisco could potentially be hiding. The map contains a list of transport links connecting pairs of cities by modes of transport. While you have no idea which city Carmen is currently in, each time she moves to a different city you will be informed of the mode of transport she used. Your task is, given this list of movements, to determine all the cities she could possibly be in after she has finished moving.


The first line of the input file will consist of two integers N M ( 2  <= N  <= 500, 1  <= M  <= 50000), separated by a space. The first integer N specifies the number of cities. The second integer M specifies the number of transport connections among these cities.

Each city is assigned a unique number from 1 to N, and each mode of transport is assigned a unique number between 1 and 1000.

The following M lines of input will each contain three space-separated integers of the form A B C, stating that it is possible to get from city A to city B via the mode of transport of type C ( 1  <= A, B  <= N, 1  <= C  <= 1000). It is guaranteed that A and B will not be the same city.

The next line of input will contain the integer K, the number of times Carmen moved between cities ( 1  <= K  <= 500). The following K lines of input will each contain a single integer representing the mode of transport Carmen used.


Your output file should list each city that Carmen could possibly be in after her K moves. Each line of the output file should contain the number of a city that Carmen could possibly be in. Each possible city should be listed once. The order of cities does not matter.

If there are no possible cities that Carmen could be in, output a single line containing the string "Impossible".

Sample Input 1

5 7
1 3 1
1 4 3
3 2 1
4 3 2
2 4 1
4 5 2
3 5 3

Sample Output 1



The following diagram represents the first sample input. Transport type 1 (train) is represented by thin dotted lines. Transport type 2 (bus) is represented by thick dotted lines. Transport type 3 (plane) is represented by solid lines.


Carmen could start at city 2 and catch a train to city 4, then a bus to 3 and back to 4, followed by a plane to city 1. Alternatively, Carmen could start at city 2, catch a train to city 3, a bus to city 4, a bus to city 5, and finally a plane to city 3. Lastly, Carmen could start at city 1, catch a train to 3, a bus to 4 and a bus back to 3, then a plane to 5.

These three cities are the only possible cities Carmen could finish in, giving the output shown above.

Sample Input 2

3 4
1 2 1
1 3 1
1 3 2
2 3 3

Sample Output 2



The second sample input consists of three cities with four transport links, as shown in the diagram below.


After the first two moves, the only city Carmen could possibly be in is city 1. In the third move, however, Carmen takes transport type 3 (plane), which is not possible from city 1. Hence, there are no solutions.


The score for each input scenario will be 100% if a correct answer is written to the output file, and 0% otherwise.


Privacy statement
© Australian Mathematics Trust 2001-2023

Page generated:  3 June 2023,  1:57pm AEST