연말 선물

질(Jill)은 대형 소프트웨어 회사의 인사 담당자입니다. 올해 사업이 잘 되어, 그녀는 연말을 맞아 모든 직원에게 작은 선물을 나눠 주려고 합니다. 각 직원이 특별하다고 느끼도록, 모든 직원은 자신이 직접 함께 일하는 사람들과는 서로 다른 선물을 받아야 합니다. 이 회사는 위계가 엄격해서, 각 사람은 자신의 직속 상사, 그리고 자신에게 직접 보고하는 사람들하고만 함께 일합니다.

질은 모두를 만족시키는 데에는 서로 다른 두 종류의 선물이면 충분하다는 것을 알아차렸습니다. 그녀는 멋진 선물 두 개를 골랐지만, 두 선물의 가격은 조금 다릅니다. 회사의 비용을 아끼기 위해, 그녀는 전체 비용이 최소가 되도록 선물을 배정하려고 합니다.

두 선물의 가격과 보고 관계가 주어질 때, 다음 조건을 만족하는 선물 배정의 최소 총 비용을 구하세요: 모든 직원의 선물은 자신의 상사의 선물과 달라야 하고, 자신에게 직접 보고하는 모든 사람의 선물과도 달라야 합니다.

첫째 줄에는 시나리오의 수가 주어집니다.

각 시나리오는 두 정수 $u$와 $v$ ($1 \le u, v \le 1000$)가 적힌 줄로 시작하며, 이는 두 선물의 가격입니다. 다음 줄에는 직원 수 $n$ ($2 \le n \le 1000$)이 주어집니다. 그다음 줄에는 공백으로 구분된 $n - 1$개의 정수 $b_1, b_2, \ldots, b_{n-1}$이 주어지며, $b_i$는 직원 $i$의 상사입니다. 모든 사람은 직접 또는 간접적으로 회사의 CEO에게 보고하며, CEO는 $0$번 직원입니다. CEO도 선물을 받습니다.

각 시나리오마다 먼저 Scenario #i: 형식의 줄을 출력합니다. 여기서 $i$는 $1$부터 시작하는 시나리오 번호입니다. 그다음 줄에 질이 선물에 써야 하는 최소 금액을 출력합니다. 각 시나리오 뒤에는 빈 줄을 하나 출력합니다.