HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > IMPC-2014-15 Questions > problem:


0th-5. 50692 - How much money?

IMPC-2014-15 Questions

Start: Nov.22.2014 at 03:00:00 PM
Finish: Nov.22.2014 at 08:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• 0th-1. 50402 - Hello World!
• 0th-2. 50403 - Number of Chairs
• 0th-3. 50763 - Valid Password
• 0th-4. 50404 - Sum of Self Powers
• 0th-5. 50692 - How much money?
• 1st-2. 50483 - Group Total
• 1st-3. 50484 - Number Of Letters
• 1st-4. 50473 - Counting Circles Posit...
• 1st-6. 50485 - Center of gravity of ...
• 2nd-1. 50522 - Multiplication Table - 2
• 2nd-2. 50512 - Coding redundancy
• 2nd-3. 50533 - Contacts List
• 2nd-5. 50793 - Top M Customers

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Prepared by : Sidrit Reka.

How much money?

Question:
Recently there have been a lot of words related to the corruption of soccer federations like FIFA and UEFA. Some of the events that leaded to these accusations were the decisions related to the World Cup 2022 in Qatar and the match Serbia vs. Albania that was a part of the Euro 2016 qualifiers. We tried to investigate a bit more about this case and finally we understood how the scheme of corruption is formed.

The corruption is shown as a set of connections that exist between individuals that know each other. If two persons A and B know each other, A can corrupt B by giving to B 100 $ and also B can corrupt A by giving to A 100 $. Let us say that there is another person C which knows person B and there is another person D which does not know anyone. Now, A can corrupt also C but he needs to pay 200 $ this time, because he can make this corruption only by paying 100 $ to B and then another 100 $ passed to C through B. If A would know C directly, he would have spent only 100 $. In this example, person D cannot corrupt anyone and cannot be corrupted since he does not know anyone else.

Input specification
You will be first given a number (n) which is the number of individuals that work in these federations where 2 <= n <= 100. Then, you will be given n strings which are the names of these individuals. After that, you will be given a number (m), where 0 <= m <= 50, which shows the number of pairs of persons that know each other, followed by (m) pairs of strings that represent these persons.In the end, you will be given 2 names, A and B, meaning that person A wants to corrupt person B.

Output specification
Print as an output the minimum amount of money that person A has to give in order to corrupt person B or print 'Impossible' if B cannot be corrupted by A.

 Sample Input I     Sample Output I   
4
Blatter
Platini
Atkinson
Karadzic
3
Platini Blatter
Atkinson Platini
Karadzic Atkinson
Karadzic Blatter
300
 Sample Input II     Sample Output II   
4
Blatter
Platini
Atkinson
Karadzic
2
Platini Blatter
Karadzic Atkinson
Karadzic Blatter
Impossible


Для отправки решений необходимо выполнить вход.

www.contester.ru