题目描述

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$ 次交换的方案，输出任意一组即可。

4 4
1 2 10
2 3 3
3 4 1
1 4 4

1
1 4

提示

翻译由 DeepSeek V3.2 完成