High School Programming League Problems Archive

Recently, Julia and Robert have become very interested in social networks and they often discuss issues related to the subject.

- "Do you trust recommendations given by people you do not know personally?" - asked Robert.

- "No."

- "But this is not the case when the source of the recommendation is someone you know?"

- "Indeed, that's different." - said Julia

- "Suppose now, that someone would like to influence the whole social network. If in the given network exists one member, say A, who is a friend of everyone else, then it is enough to control A's account to influence the whole network."

- "Oh, do you suggest that whether the network is resistant to such attacks or not depends on its structure?"

- Exactly! ....

A few hours later they both agreed on the following model. There is a social network of n members with a symmetric friendship relation (that is if A is a friend of B then also B must be a friend of A). In addition, with each member A there is associated a positive integer W(A). We consider W(A) as the cost of taking over control of A's account.

Now, they are looking for a subset of members D, such that every member of the network is in D or is a friend of someone in D, and the sum of W(A) for all A in D is as small as possible. You are asked to help them to solve the problem!

Task: Write a program which is able to find such subsets efficiently.

Input

Given: n - the number of social network members and in the next n lines:
name_i W(name_i) - the name of the i-th member (a sequence of at most 15 characters) and the corresponding integer 1 <= W(name_i) <= 250.

Next, m - the number of friendship relations, and in each of the following m lines
name_x name_y - the names of two linked members, name_x != name_y.

Output

In the first line print d, the number of members in D and in the following d lines: name_i - the name of the i-th member in D. In the last line print one integer - the sum of W(A) for all A in D.

Scoring

The score awarded to your program for a given test is computed as S/S_d, where S is the sum of W(A) for all A in the network, while S_d is the sum of W(A) for all A in D. The overall score of the program is the sum of scores obtained for correctly solved tests.

The number of points given in the ranking is scaled so that it is equal to 10 for the registered contestant whose solution has the highest score, and proportionally less for all solutions with lower scores.

Example

Input:
5
Robert 12
Julia 23
Adam 1
Carol 10
Daniel 4
5
Robert Julia
Robert Carol
Adam Robert
Daniel Adam
Daniel Julia 

Output:
2 
Daniel 
Carol
14

Scoring:
The exemplary solution will score 50/14 points.

Input data sizes

 t     n     m    l 
 1    100    99    2s
 2    100   101    2s
 3    100   105    2s
 4    100   114    2s
 5    100   130    2s
 6    300   299    5s   
 7    300   302    5s 
 8    300   311    5s
 9    300   339    5s
10    300   404    5s

 t - testcase number 
 n - the number of social network members
 m - the number of friendship relations
 l - time limit

Please note

• Till the last week of the series, all submitted codes will be visible to all users and tested on temporary data sets only.
• For the last week of the series, submissions will be visible to the submitting contestant, only, and tested on the full set of test cases. (All earlier solutions will be rejudged).