SP1964 MMCUT - Tree cut

You are given a tree (a connected, acyclic graph) along with a set of **commodities**, i.e. pairs of vertices, (_s $ _{1} $_ ,_t $ _{1} $_ ),...,(_s $ _{m} $_ ,_t $ _{m} $_ ) (_s $ _{i} $_ ≠ _t $ _{i} $_ ). A **multicut** is a set of edges that when removed disconnects _s $ _{i} $_ from _t $ _{i} $_ for all _i_. There is a unique path _P $ _{u,v} $_ between every pair of vertices _u,v_ in a tree, and the **max-cost** of a multicut _S_ is max $ _{i} $ |_S_ ∩ _P $ _{si} $ , t $ _{i} $_ |. You will be given a rooted tree of height _1_ and a set of commodities and must return the minimum possible max-cost over all multicuts.

The first line of the input is "_N M_" (_1_ ≤ _N, M_ ≤ _100000_), where _N_ is the number of vertices in the tree and _M_ is the number of commodities. All vertices are numbered _0, ...,N-1_, and the root has label _N - 1_. _M_ lines then follow, where the _i_th line is "_s $ _{i} $ t $ _{i} $_ ", representing a commodity (_s $ _{i} $_ , _t $ _{i} $_ ) where _s $ _{i} $_ ≠ _t $ _{i} $_ . Commodities are distinct: neither (_s $ _{i} $_ , _t $ _{i} $_ ) = (_s $ _{j} $_ , _t $ _{j} $_ ) nor (_s $ _{i} $_ , _t $ _{i} $_ ) = (_t $ _{j} $_ , _s $ _{j} $_ ) will hold when _i_ ≠ _j_.

Your output should consist of a single number, the minimum possible max-cost of a multicut, followed by a newline.