MMCUT - Tree cut
You are given a tree (a connected, acyclic graph) along with a set of commodities, i.e. pairs of vertices, (s1,t1),...,(sm ,tm) (si ≠ ti). A multicut is a set of edges that when removed disconnects si from ti for all i. There is a unique path Pu,v between every pair of vertices u,v in a tree, and the max-cost of a multicut S is maxi |S ∩ Psi, ti|. 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 ith line is "si ti", representing a commodity (si, ti) where si ≠ ti. Commodities are distinct: neither (si, ti) = (sj, tj) nor (si, ti) = (tj, sj) 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.
Input: 10 2 0 5 4 8 Output: 1