27G. Soap Warehouse

3500 pts4s512 MB

A warehouse contains $n$ rooms connected by corridors that form a tree. Each corridor has a length. Room $i$ contains one bar of soap described by $s_i$ : hand soap (H) or face soap (F).

You start in room $1$ . Collect every bar of soap exactly once and finish in room $1$ . You may visit rooms and traverse corridors any number of times; visiting a room does not force you to collect its soap.

The required types of collected soap alternate as hand, face, hand, face, and so on. On a hand turn, you may collect either type of soap. On a face turn, you may collect only face soap.

Find the minimum possible total length of all traversed corridors. If it is impossible to collect all bars under these rules, output $-1$ .

Constraints

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$n$ is even.
The sum of $n$ over all test cases does not exceed $2 \times 10^5$ .
$s$ is a string of length $n$ consisting only of H and F.
$1 \le u_i, v_i \le n$
$1 \le w_i \le 10^6$
The $n-1$ corridors form a tree.

Input

t

\left. \begin{array}{l} n \\ s_1s_2\ldots s_n \\ u_1\quad v_1\quad w_1 \\ u_2\quad v_2\quad w_2 \\ \vdots \\ u_{n-1}\quad v_{n-1}\quad w_{n-1} \end{array} \right\} \times t

Output

\mathrm{answer}\;\} \times t

Samples

Input

Case 1

2
FF
1 2 5

Case 2

Explanation

Case 1

Collect the soap in room $1$ on a hand turn and the soap in room $2$ on a face turn, then return. The corridor is traversed twice, for a total distance of $10$ .

Case 2

There are two face turns, but only one bar of face soap, so collecting all the soap is impossible.

Output

Case 1

Case 2

-1

Input

Case 1

Case 2

Case 3

Explanation

Case 1

Collect the soaps in rooms $2,4,3,1$ , in that order. Pass through room $3$ on the way to room $4$ without collecting its soap yet. The total distance is $6$ .

Case 2

Collect the soaps in rooms $1,4,2,5,3,6$ , in that order, then return to room $1$ . The total distance is $18$ .

Case 3

Collect the soaps in rooms $1,3,2,4,5,6$ , in that order, then return to room $1$ . The face soap in room $5$ fills a hand turn. The total distance is $12$ .

Output

Case 1

Case 2

Case 3

A warehouse contains $n$ rooms connected by corridors that form a tree. Each corridor has a length. Room $i$ contains one bar of soap described by $s_i$ : hand soap (H) or face soap (F).

The required types of collected soap alternate as hand, face, hand, face, and so on. On a hand turn, you may collect either type of soap. On a face turn, you may collect only face soap.

Find the minimum possible total length of all traversed corridors. If it is impossible to collect all bars under these rules, output $-1$ .

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$n$ is even.
The sum of $n$ over all test cases does not exceed $2 \times 10^5$ .
$s$ is a string of length $n$ consisting only of H and F.
$1 \le u_i, v_i \le n$
$1 \le w_i \le 10^6$
The $n-1$ corridors form a tree.

t

\left. \begin{array}{l} n \\ s_1s_2\ldots s_n \\ u_1\quad v_1\quad w_1 \\ u_2\quad v_2\quad w_2 \\ \vdots \\ u_{n-1}\quad v_{n-1}\quad w_{n-1} \end{array} \right\} \times t

\mathrm{answer}\;\} \times t

Collect the soap in room $1$ on a hand turn and the soap in room $2$ on a face turn, then return. The corridor is traversed twice, for a total distance of $10$ .

Collect the soaps in rooms $2,4,3,1$ , in that order. Pass through room $3$ on the way to room $4$ without collecting its soap yet. The total distance is $6$ .

Collect the soaps in rooms $1,4,2,5,3,6$ , in that order, then return to room $1$ . The total distance is $18$ .

Collect the soaps in rooms $1,3,2,4,5,6$ , in that order, then return to room $1$ . The face soap in room $5$ fills a hand turn. The total distance is $12$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

27G. Soap Warehouse

Constraints

Input

Output

Samples

27G. Soap Warehouse

Constraints

Input

Output

Samples