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
|
Для отправки решений необходимо выполнить вход.
|