Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

HS12TRPL - Triples

You are given a group G of n people and a symmetric relation R between them (we interpret pRq for example as follows: p is able to work with q and vice versa). Your task is to partition as large a subset of G as possible into working groups of three people in such a way that for every triple (p,q,r), the group leader p is able to work with the other two members of the group (i.e., pRq and pRr).

Input

Given: n - the number of people and in the next n lines:
namei W(namei) - the name of the i-th person (a sequence of at most 15 characters) and the corresponding integer 1 <= W(namei) <= 100.

Next, m - the number of elements in relation R, and in each of the following m lines
namex namey - the names of two related people, namex != namey.

Output

In the first line print g, the number of groups in your solution and in the following g lines: namep nameq namer - names of people in the consecutive group (the name of the leader first). In the last line print one integer Sg- the sum of 2*W(namep)+W(nameq)+W(namer) taken over all groups.

Scoring

The score awarded to your program for a given test is simply Sg. 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:
7
Adam 4
Carol 3
Daniel 3
Robert 4
Julia 5
Frank 3
Henry 5
7
Adam Carol
Carol Daniel
Carol Julia
Adam Robert
Robert Julia
Julia Frank
Robert Henry


Output:
2 
Julia Carol Frank
Robert Adam Henry 
33

Scoring:
The exemplary solution will score 33 points.

Input data sizes

 t     n     m    l 
 1    120   119    2s
 2    120   121    2s
 3    120   123    2s
 4    120   130    2s
 5    120   145    2s
 6    270   269    5s
 7    270   287    5s
 8    270   292    5s
 9    270   312    5s
10    270   341    5s

 t - testcase number 
 n - the number of people
 m - the number of 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).

Added by:kuszi
Date:2012-10-27
Time limit:0.400s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 ASM64 BASH BF C CSHARP C++ 4.3.2 CPP C99 CLPS CLOJURE LISP sbcl LISP clisp D ERL FSHARP FORTRAN GO HASK ICON JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PERL6 PHP PIKE PRLG-swi PYTHON PYTHON3 RUBY SCALA SCM guile SCM qobi ST TCL WHITESPACE
Resource:High School Programming League

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.