Internet Problem Solving Contest

• Easy input data set – L1
• Hard input data set – L2

Once upon a time there was the kingdom of Absurdistan. There were N cities in the kingdom.

As it is often the case, some pairs of cities were connected by roads. The Great Vizier of Absurdistan was a terrible scrooge, hence the road network was a tree. (I.e., for any pair of cities there was exactly one way how to get from one to the other, while travelling by roads.)

The roads were made of concrete blocks and they all had a dull grey color.

One day, the Great Vizier came to the conclusion that travelling along dull grey roads makes people unhappy. As he does not want to risk a revolution, he decided to paint the roads using happy colors – the 7 colors of the rainbow.

Each day, he picked two cities s_i and t_i, and a color c_i. Painters with an ample supply of the color c_i were sent to the city s_i, and then they travelled to t_i. On their way, whenever they encountered a road that did not have the color c_i, they painted it to this color.

Problem specification

You are given the number of cities N, the description of the road network, and the sequence of Great Vizier’s orders.

For each order, compute the number of roads the painters had to repaint.

Input specification

The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.

Each test case starts with line containing a positive integer N (N ≤ 1000000). For convenience, the cities in Absurdistan are numbered 0 to N - 1.

N - 1 lines follow. Each of these lines contains two numbers a_i b_i (0 ≤ a_i,b_i < N) – the endpoints of one road.

The next line contains a single integer Q (Q ≤ 200000) specifying the number of orders.

Q lines follow, each describing one order. Each description consists of two integers s_i t_i (0 ≤ s_i,t_i < N) and a string c_i (c_i is one of red, orange, yellow, green, blue, indigo, and violet).

In the easy input, you may also assume that for each test case except for one we have NQ ≤ 10⁸. In the remaining test case the road network is a simple line.

Output specification

For each test case output seven lines. Each of these lines should contain a color name (in the order given above) and a number. The number shall be the total number of times some road was painted using the corresponding color.

You may output empty lines between the test cases. (The amount of whitespace in your output does not matter anyway; we do this for readability in the example below.)

Example

input 2 8 0 4 7 5 5 6 3 5 1 4 4 2 4 3 4 0 7 red 2 6 orange 4 3 green 1 7 green 12 0 1 1 2 2 3 2 4 2 5 0 6 6 7 7 8 7 9 7 10 11 6 3 3 8 blue 6 1 violet 5 11 blue

output red 4 orange 4 yellow 0 green 4 blue 0 indigo 0 violet 0 red 0 orange 0 yellow 0 green 0 blue 10 indigo 0 violet 2 We will explain the second test case in detail: When executing the query “3 8 blue”, we paint six roads blue: 3-2, 2-1, 1-0, 0-6, 6-7, and 7-8. When executing the query “6 1 violet”, we paint two roads violet: 6-0 and 0-1. (Both of these roads were previously blue.) Finally, when executing the query “5 11 blue”, we paint four roads blue: 5-2, 1-0, 0-6, and 6-11. Note that the road 2-1 was still blue, hence we did not paint it now. Thus we painted a road blue 6+4=10 times, and we painted a road violet 2 times.