Tuenti Challenge 7

Challenge 11 - Colors

galaxies

You are a conscious sphere of energy. You live in an abstract, colorful world, formed by clumps of energy vibrating at different frequencies and other beings like you. Your kind can absorb residual energy from the environment, which makes them change color. For example, if you are Red and you absorb Blue energy you would become Purple. Note that if you are Purple and you absorb Blue again, nothing would happen: you already have Blue energy in you. In the beginning your energy is neutral (transparent, if you like). What's more, while some color combinations may not have names, they are still possible (for example, Purple + Green).

Your world began in a similar way to the human one: at first, all the energy was concentrated together in a single point, but now it has all expanded and drifted away, with gravity clustering everything into groups. We call each of these groups a Galaxy. The distance between galaxies is unbelievably long but, thankfully for you, some of them are connected by wormholes. A wormhole functions as a tunnel, transporting you instantly from one side to the other. The wormholes in your universe are very special:

  • They are unidirectional.
  • They absorb energy too, but only those of certain specific frequencies. A Red wormhole, for example, absorbs Red energy.
  • You need to have the same color energy as the wormhole in order to go through it.

This may seem complicated but, it's actually really simple: if you are Purple and you go through a Blue wormhole, you will become Red. After that you cannot go through a Blue wormhole as you don't have Blue energy, unless you absorb Blue energy again. Galaxies are very different from each other and some have colored environmental energy floating around, but the problem is that it takes a considerable amount of time to gather enough of it to change your color.

You have been in Galaxy 0 your entire existence and you are growing a bit bored, so you have decided that it's time for you to do some traveling. You want to know the fastest way to reach each Galaxy in order to decide your travel destination. The time to reach Galaxy 0 is always 0 (you are already there!)

Input

The first line will contain an integer C, the number of cases for our problem.

Each case starts with a line with one integer K, the number of colors. A set of K lines follows, each describing a color. The description of a color consists of a string N (the name of the color) and an integer M, followed by M strings. This means that the color N is composed of a mix of the M colors. Primary colors have M = 0.

Next comes a line with an integer G, the number of Galaxies. G galaxies descriptions follow. Each description starts with a line with an integer E, the number of different energies present in that galaxy. A set of E lines follows, each with a string X and an integer T, indicating that the energy of color X takes T seconds to gather.

A line with an integer W, the number of wormholes, follows. A set of W lines follows, each describing a wormhole. The description of a wormhole consists of a string H, the color of the wormhole, and two integers A and B, indicating that the wormhole goes from Galaxy A to Galaxy B.

Output

For each case, a line starting with "Case #x: " followed by the sequence of G space-separated integers, indicating the minimum time to reach each Galaxy. If it's not possible to reach a galaxy, print -1 instead.

Example

4
Red 0
Green 0
Blue 0
Yellow 2 Red Green
5
2
Red 10
Green 10
2
Red 15
Green 15
2
Blue 7
Green 5
1
Red 11
2
Red 10
Green 10
6
Red 0 1
Red 3 2
Green 1 2
Blue 0 3
Blue 3 4
Yellow 2 0

It might help to have a visual representation of the case too:

Example case

The minimum time to reach Galaxy 0 is 0.
The minimum time to reach Galaxy 1 is 10: From 0, gather Red energy and go to 1.
The minimum time to reach Galaxy 2 is 20: From 0, gather Red and Green energy. Go to 1 and then to 2.
The minimum time to reach Galaxy 3 is 47: From 0, gather Red and Green energy. Go to 1 and gather Red energy again. Go to 2 and gather Green and Blue energy. Go back to 0, and then go to 3.
You cannot reach Galaxy 4.

Limits

  • 1 ≤ G ≤ 500
  • 1 ≤ Primary colors ≤ 10
  • 1 ≤ W ≤ 20000

Sample Input

1
4
Red 0
Green 0
Blue 0
Yellow 2 Red Green
5
2
Red 10
Green 10
2
Red 15
Green 15
2
Blue 7
Green 5
1
Red 11
2
Red 10
Green 10
6
Red 0 1
Red 3 2
Green 1 2
Blue 0 3
Blue 3 4
Yellow 2 0

Sample Output

Case #1: 0 10 20 47 -1

Test your code

You can test your program against both the input provided in the test phase and the input provided in the submit phase. A nice output will tell you if your program got the right solution or not. You can try as many times as you want to. Be careful with extra whitespaces, the output should be exactly as described.

Test your program against the input provided in the test phase

Download test input

Program output:

Test your program against the input provided in the submit phase

Download input

Program output:

During the submit phase, in some problems, we might give your program harder inputs. As with the test token, a nice output will tell you if your program got the right solution or not. You can try as many times as you need.

In the actual contest you first need to solve the test phase before submitting the code, you must provide the source code used to solve the challenge and you can only submit once (once your solution is submitted you won't be able to amend it to fix issues or make it faster).

If you have any doubts, please check the info section.