On Average They're Purple

This problem gives us a graph and asks us to 2-color it such that for all paths from a pre-specified u->v, the minimum number of transitions between the two colors is maximized. i.e. we walk every path from u->v, and find the minimum number of transitions. We want to choose the coloring that MAXIMIZES this minimum.

It should be clear that we can't find a maximum greater than the shortest-path from u->v, as an adversarial chooser can always choose the shortest path, limiting our maximum to that value. Thee question then becomes, can we ever do WORSE than the shortest path, and the answer is, no. If we color nodes in level sets (i.e. nodes distance 1 from u are red, nodes distance 2 are blue...etc), we will always make a color change as we move one step further from u->v.

Therefore, as we cannot do better than the shortest distance, and can ALWAYS force at least the shortest distance, the answer will always be the shortest distance from u->v. We can simply BFS to find the answer.