Holiday Gifts

Jill is a human-resources manager at a large software company. Because the year went well, she wants to give every employee a small gift for the holiday season. To make each person feel special, every employee must receive a gift that is different from the gifts given to the people they work with directly. The company has a strict hierarchy: a person works only with their immediate boss and the people who report directly to them.

Jill realizes that two different gifts are enough to make everyone feel special. She picks two nice gifts, but they cost slightly different amounts. Always trying to save money for her company, she wants to assign the gifts so that she spends as little as possible.

You are given the prices of the two gifts and the reporting structure. Compute the minimum total cost of an assignment that satisfies the following condition: every employee's gift must differ from their boss's gift and from the gift of everyone who reports directly to them.

The first line contains the number of scenarios.

Each scenario begins with a line containing two integers $u$ and $v$ ($1 \le u, v \le 1000$), the prices of the two gifts. The next line contains the number of employees $n$ ($2 \le n \le 1000$). The following line contains $n - 1$ integers $b_1, b_2, \ldots, b_{n-1}$ separated by spaces, where $b_i$ is the boss of employee $i$. Everyone reports, directly or indirectly, to the company's CEO, who is employee number $0$. The CEO also receives a gift.

For each scenario, print a line Scenario #i:, where $i$ is the scenario number starting at $1$. On the next line, print the minimum amount of money Jill must spend on gifts. Print a blank line after each scenario.