Statement

The railway network in the Pordenone county consists of N train stations connected by N-1 tracks (X_i, Y_i) so that from every station is possible to reach any other station: in other words, the tracks form a tree. This choice makes the transportation system extremely inefficient: trains going in opposite directions cannot cross each other on a single track, so they need to perform lengthy and complex manoeuvres to pass each other. The new administration founded its campaign trail on changing this situation once and for all… and now it's time to keep promises! Edoardo, the local leading expert in logistics, already has a mind-blowing idea for fixing the situation: making each track one-way, so that no crossings will ever occur! Of course, the tricky part is choosing the orientations so that the service remains acceptable for the majority of the population. After inspecting the traffic patterns, Edoardo discovered that most people travel between one of M pairs (A_i, B_i) of stations...