High School Programming League Problems Archive

In the MathUniverse traveling between galaxies is possible thanks to bidirectional hypertunnels. Each hypertunnel connects exactly two galaxies. During the last few billion years, in which intergalactic trade has become an essential element of the MathUniverse economy, it has become a priority to guarantee a sens of security and stability. To achieve this aim, the ISO (Intergalactic Security Organization) was founded. However, very soon it turned out that ISO is unable to carry out its duties because of its long time of reaction to conflicts. So, it has been decided that ISO should have multiple bases, with at least one base existing no further than one hypertunnel away from each of the galaxies. Now, the task is to design a placement of bases so as to minimize the cost of the whole project. Given all the galaxies, the costs of bases (dependent on the galaxy of their location), and the arrangement of hypertunnels, you must select some galaxies as locations of ISO bases.

Input

Given: n - the number of galaxies and in the next n lines:
name_i c_i - the name of the i-th galaxy (a sequence of at most 10 characters) and the corresponding cost of a base - an integer 1 <= c_i <= 100.

Next, m - the number of hypertunnels, and in each of the following m lines
name_j1 name_j2 - the names of two galaxies connected by the tunnel.

Output

First output k the number of bases and in the following k lines: name_i - the name of the i-th galaxy to place the ISO base at, and in the last line: cost the total cost of all the bases.

Scoring

The score awarded to your program for a given test is computed as C/C_p, where C_p is the cost obtained by your program, and C is some constant (a reference cost). 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:
8
SmallCloud 5
LargeCloud 3
LeoA 3
CetusDwarf 5
MilkyWay 4
Andromeda 4
NGC185 3
AndI 6
9
SmallCloud LargeCloud 
LargeCloud Andromeda
Andromeda CetusDwarf
CetusDwarf AndI
CetusDwarf MilkyWay
AndI MilkyWay
AndI NGC185
MilkyWay LeoA
LeoA SmallCloud


Output I:
3
MilkyWay
NGC185
LargeCloud
10

Scoring: Assuming that the relative cost C for this test is equal to 12, the exemplary solution will score 12/10 points.

Output II:
3
LeoA
NGC185
LargeCloud
9

This answer would be judged as wrong becouse CetusDwarf is more than one hypertunnel away from the nearest of the planned bases.

Input data sizes

Approximate test data sizes are given below.

 t     n     m    l 
 1    10    15    1s
 2    20    30    2s
 3    30    40    2s
 4    40    70    2s
 5    60    90    2s
 6    90   130    2s
 7   100   130    2s
 8   110   170    2s
 9   120   130    2s
10   130   140    2s
11   140   180    2s
12   150   260    2s
 t - testcase number 
 n - the number of galaxies
 m - the number of hypertunnels
 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).