P5934 [Tsinghua Training 2012] Minimum Spanning Tree

Given a connected undirected graph $G=(V,E)$ with positive edge weights, where $N=|V|$ and $M=|E|$. The $N$ vertices are numbered from $1$ to $N$. Given three positive integers $u, v$ and $L$ $(u \ne v)$, suppose we now add an edge $(u, v)$ with weight $L$. What is the minimum number of edges that must be deleted so that this edge can appear in some minimum spanning tree, and can also appear in some maximum spanning tree?

The first line contains two integers separated by spaces, which are $N$ and $M$. The next $M$ lines each contain three positive integers $u, v$ and $w$, indicating that in graph $G$ there is an edge between $u$ and $v$ with weight $w$. The last line contains three integers separated by spaces, which are $u, v$ and $L$. The testdata guarantees that there are no self-loops in the graph.

Output one line with one integer, indicating the minimum number of edges that need to be deleted.

#### Sample Explanation We only need to delete edge $(1,2)$. After deleting it and adding the new edge, the spanning tree of the graph becomes unique. #### Constraints For $20\%$ of the testdata, $N\leqslant10, M\leqslant20, L\leqslant20$. For $50\%$ of the testdata, $N\leqslant300, M\leqslant3000, L\leqslant200$. For $100\%$ of the testdata, $N\leqslant20000, M\leqslant200000, L\leqslant20000$. Translated by ChatGPT 5