SP1964 MMCUT - Tree cut

你需要处理一棵树（其实就是一个连接起来且不成环的图结构），以及多个**商品**，即顶点对，例如 (_s_ $_1$, _t_ $_1$), ..., (_s_ $_m$, _t_ $_m$)，其中对于每对顶点 s 和 t 来说，s 和 t 是不同的。所谓多割，是指一组边的集合，当这些边被移除后，能够使得所有的顶点对 (_s_ $_i$, _t_ $_i$) 都不连通。由于在树中每两个顶点之间都有唯一的一条路径 _P_ $_{u,v}$，一个多割的**最大代价**定义为对每一个商品对 (_s_ $_i$, _t_ $_i$)，都求出路径 _P_ $_{s_i, t_i}$ 与割集 _S_ 的交集大小，然后取这些交集大小的最大值。你得到的是一棵高度为 1 的有根树和一组商品，目标是找出所有可能的多割中，最大代价的最小值。

第一行输入两个整数 _N_ 和 _M_，分别代表树中的顶点数和商品的数量（1 ≤ _N, M_ ≤ 100000）。顶点从 0 到 _N-1_ 编号，编号为 _N-1_ 的点是根节点。接下来有 _M_ 行，每行两个整数 _s_ $_i$ 和 _t_ $_i$，表示一对商品 (_s_ $_i$, _t_ $_i$)，且 _s_ $_i$ 和 _t_ $_i$ 总是不同的。所有的商品对都不重复：即不论 _i_ ≠ _j_，都不会有 (_s_ $_i$, _t_ $_i$) 等于 (_s_ $_j$, _t_ $_j$) 或 (_t_ $_j$, _s_ $_j$)。

输出一个整数，表示能够实现的多割的最小可能的最大代价，然后换行。 **本翻译由 AI 自动生成**