|
J |
Jewel
Transportation Input: Standard Input Output: Standard Output |
|
A rich company wants to send k kinds of jewels from their factories to
destinations. Different jewels can have different factories and destinations.
To ensure that the transportation of the jewels are not influenced by unknown
factors, the company decided to buy all the roads that are needed and install
special transportation facilities on each road. No roads can be used to
transport two or more kinds of jewels, so every two kinds of jewels must follow
two edge-disjoint paths from their own factories to destinations.
Help the company to minimize the cost to buy the roads and install the
facilities.
Input
The input consists of at most 10
test cases. Each case contains three integers n, m and k (1 ≤ n ≤ 16, 1≤ m ≤ 100, 1 ≤ k ≤ 5), the number of cities, the number of
roads and the number of kinds of jewels. Each of the following m lines begins with two different
integers a, b, and then followed by k
integers ci (1≤ ci ≤ 1000),
describing a directed road from city a
to city b, with cost ci if you install facilities
for transporting the i-th jewel. Cities are numbered 1 to n. Each of the last k
lines describes one kind of jewel by two integers s and t, that is the city
of factory and destination. The last test case is followed by three zeros,
which should not be processed.
Output
For each test case, print the minimal cost in
the first line (if there is no solution, print -1). If there is a solution,
print k lines one for each kind of
jewel. The first integer is the number of roads, then a list of roads. Roads
are numbered 1 to m in the order they appear in the input.
Sample
Input
Output for Sample Input
|
4 10 2 1 3 27 50 4 1 45 23 2 3 13 24 4 2 12 64 2 4 93 45 4 1 89 12 3 4 5 83 3 2 76 35 3 2 10 48 3 1 34 29 3 2 3 4 0 0 0 |
90 1 9 2 5 8 |