깨진 최소 스패닝 트리

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$)가 주어진다. 이는 가중치 $w$인 간선이 정점 $u$와 $v$를 잇는다는 뜻이다. 간선은 $1$부터 $m$까지 번호가 매겨져 있다.

그래프는 연결되어 있다. 입력의 처음 $n-1$개 간선은 Ethan의 초기 스패닝 트리이다. 그래프는 단순 그래프가 아닐 수 있어서, 같은 두 정점 사이에 간선이 여러 개 있을 수 있다.

최소 간선 교환 횟수 $k$를 정수 하나로 출력한다. 이는 스패닝 트리를 최소 스패닝 트리로 만드는 데 필요한 최소 횟수이다. 이어서 $k$개의 줄에 정수 $a$와 $b$를 출력한다. $a$는 제거할 간선의 번호, $b$는 추가할 간선의 번호이다. $k$번의 교환이 문제를 해결하는 방법이 여러 가지라면, 그중 어느 것을 출력해도 된다.