P16071 [ICPC 2023 NAC] Broken Minimum Spanning Tree

Ethan 的任务是在一个带权连通无向图中找到一棵最小生成树。然而，他误解了任务，找到了一棵可能并非最小的生成树。为了让他的生成树成为最小生成树，你需要执行一系列边交换操作。一次边交换操作会从当前生成树中删除一条边，并从图中添加一条当前不在生成树中的边。每次交换后，得到的图仍然必须是一棵生成树。请问，修复 Ethan 的生成树使其成为最小生成树所需的最少边交换次数是多少？

输入的第一行包含两个整数 $ n $（$ 2 \le n \le 2{,}000 $）和 $ m $（$ n - 1 \le m \le 3{,}000 $），其中 $ n $ 是图中的节点数，$ m $ 是图中的边数。节点编号为 $ 1 $ 到 $ n $。 接下来的 $ m $ 行，每行包含三个整数 $ u $、$ v $（$ 1 \le u, v \le n, u \ne v $）和 $ w $（$ 1 \le w \le 10^9 $），表示连接节点 $ u $ 和 $ v $ 的一条权值为 $ w $ 的边。边的编号按输入顺序从 $ 1 $ 到 $ m $。 保证图是连通的。输入的前 $ n - 1 $ 条边是 Ethan 最初得到的生成树。图可能不是简单图，即同一对节点之间可能存在多条边。

输出第一行一个整数 $ k $，表示将生成树变为最小生成树所需的最少边交换次数。接下来输出 $ k $ 行，每行两个整数 $ a $ 和 $ b $，其中 $ a $ 是要删除的边的编号，$ b $ 是要添加的边的编号。如果有多组 $ k $ 次交换的方案，输出任意一组即可。

翻译由 DeepSeek V3.2 完成