P4374 [USACO18OPEN] Disruption P

Farmer John 自豪于他所经营的交通发达的农场。这个农场由 $N$ 块牧场（$2 \leq N \leq 50,000$）组成，$N-1$ 条双向道路将它们连接起来，每条道路的长度均为 $1$ 单位。Farmer John 注意到，从任何一块牧场到另一块牧场，都能通过一组合适的道路到达。 尽管 FJ 的农场现在是连通的，他担心如果有一条道路被阻断会发生什么，因为这会将农场分为两个不相交的牧场集合，奶牛们只能在每个集合内移动而不能在集合间移动。于是 FJ 又建造了 $M$ 条额外的双向道路（$1 \leq M \leq 50,000$），每条道路的长度都是一个至多为 $10^9$ 的正整数。奶牛们仍然可以使用原有的道路进行移动，除非其中的某些被阻断。 如果某条原有的道路被阻断，农场就会被分为两块不相交的区域，那么 FJ 会从他的额外修建的道路中选择一条能够重建这两块区域连通性的道路，取代原来的那条，从而使奶牛们又可以从任何一块牧场去往另一块牧场。 对于农场上每一条原有的道路，帮助 FJ 选出最短的替代道路。

无

无

供题：Brian Dean