해체

$N$개의 정점과 $M$개의 간선으로 이루어진 무방향 연결 그래프가 주어진다. 정점에는 $1$부터 $N$까지, 간선에는 입력으로 주어지는 순서대로 $1$부터 $M$까지 번호가 붙어 있다. $i$번 정점의 무게는 $W_i$이다. 자기 자신을 잇는 간선과 같은 두 정점을 잇는 중복 간선은 없다.

그래프의 모든 간선을 제거하려고 한다. 다음 연산을 정확히 $M$번 수행한다.

1. 아직 남아 있는 간선 하나를 골라 제거한다. 그 간선의 두 끝점을 $u,v$라고 하자.
2. 간선을 제거한 직후에 남은 간선들을 따라 $u$에서 $v$로 이동할 수 있는지 확인한다.

• 이동할 수 있다면, 연산 비용은 $\min(W_u,W_v)$이다.
• 이동할 수 없다면, 연산 비용은 $\max(W_u,W_v)$이다. 이 경우에는 원래 하나로 연결되어 있던 부분이 둘로 나뉜다.

모든 간선을 제거하는 데 드는 총비용의 최솟값과, 그 비용을 달성하는 간선 제거 순서를 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 테스트 케이스에 대해 다음 두 줄을 입력 순서대로 출력한다.

• 첫째 줄에 모든 간선을 제거하는 데 드는 총비용의 최솟값을 출력한다.
• 둘째 줄에 그 비용을 달성하는 간선 제거 순서를 $M$개의 간선 번호로 출력한다. $1$부터 $M$까지의 각 번호가 정확히 한 번씩 나타나야 한다.

최소 비용을 달성하는 제거 순서가 여러 가지라면 그중 아무거나 하나를 출력한다.

• $1\leq T\leq100\,000$.
• $2\leq N\leq200\,000$.
• $N-1\le$.