Almost half of numbers are divisible by two.

For the string shouldn't be any i ≤ n - 2, s_i = s_i + 2. Make some examples of little sizes.

Find minimum weighted edges.

There is some edges with weight 0, try to connect them in a carefully way.

The last situation is some 'a' characters after some 'b' ones.

The last situation is unique.

The number of steps is also unique.

Each 'b' character makes a number of 'b' characters in the last situation according to the number of 'a' characters before it.

We want to color the ice creams in a way that all of ice creams in a vertex would be different with this condition that if two vertices u and v have ice cream i, then all of vertices in the unique path of u and v would have it.

Let's have a trivial lower-bound for the answer.

You can prove that by induction on leaves of the tree. And code it how you proved it.

Let's solve the problem for just two tree.

consider this trivial solution and try to improve it to .

You can prove, we need even number of swaps to reach the same permutation. So and the answer for 4·k + 3 and 4·k + 4 is -1.

The solution almost is constructive.

Let's partition n = 4·k numbers to classes, each class contains a 4 consecutive numbers. And when n = 4·k + 1 there is a class with 5 consecutive numbers.

The problem consists two parts, the first part is to find mn_i and mx_i, the minimum and the maximum score i-th vertex may get after the score distribution. The second part is to finding the answer and all your need to solve this part is those two arrays. It is trivial mn_i is number of real bullion of golds in i-th vertex.

Let's find the scores for two vertices u and v, u have a directed edge to v.

u -> v

If i-th element from u-th vertex was painted and j-th element from v-th vertex was unpainted such that then j-th element from v-th vertex will be painted quickly. For two vertex, we can do it in complexity .

If we have this directed walk {w₁, w₂, ..., w_k}, you should affect v₁ on v_k how I said in the previous hint with .

What about strogly connected components.

In this components if i-th element from u-th vertex was painted then for all of j such that , j-th element from all vertices will be painted quickly. For this components, we can do it with complexity . In the main problem, we can suppose all of a strongly conected component a vertex with size g in this way and we can calculate mx_i with answer of its component's vertex multiplied by .

SCC of the tournament yields a Hamiltonian path of strongly connected components( if we consider each component a vertex ). The problem decreased to solve this path. we can solve the path with the complexity of sum of vertices' sizes.

Now, for every vertex we have minimum and maximum score it may get. For B known vertices, to check if they can be the wanted set, we can assume their score be maximum possible and the other scores be minimum possible. If they were top, then they can be a sample of the wanted set.

Consider a sorted sequence of combination of two array mn and mx.

For every vertex, consider the number of ways it(with its maximum score) can be the minimum score of the set of B vertices.