There are $n/2$ hand turns and $n/2$ face turns. Every hand soap must use a hand turn, while face soap may use either kind.

If there are fewer than $n/2$ face soaps, print $-1$. Otherwise, choose exactly $n/2$ original face soaps for face turns. All remaining soaps use hand turns.

Label a hand-turn vertex $+1$ and a face-turn vertex $-1$. The total label sum is zero.

For a fixed assignment, we need a closed walk whose pickups alternate between the two labels. The tree is connected, so any pickup order can be followed. First we find the cheapest route for fixed labels; then we optimize the assignment.