이븐 그래프

다다스는 최근 그래프를 정리하는 새로운 규칙을 만들었다. 이 규칙에 따르면, 무향 그래프가 아름답기 위해서는 그래프의 모든 연결 컴포넌트가 이븐이어야 한다.

무향 그래프의 각 간선은 두 색 중 하나로 칠해져 있으며, 색은 $0$ 또는 $1$로 표현된다. 연결 컴포넌트가 이븐이라는 것은, 그 연결 컴포넌트에 속한 색 $0$ 간선의 개수와 색 $1$ 간선의 개수가 같다는 뜻이다. 연결 컴포넌트가 간선을 하나도 포함하지 않는 경우, 두 색의 간선 개수가 모두 $0$으로 같으므로 이븐이다.

처음에 주어진 그래프는 이븐이 아닐 수 있다. 다다스는 그래프를 아름답게 만들기 위해 몇 개의 간선을 삭제하려고 한다. 간선을 삭제하면 그래프의 연결 상태가 바뀔 수 있으며, 삭제 후 모든 연결 컴포넌트가 이븐이어야 한다.

삭제해야 하는 간선 개수의 최솟값을 구하고, 최솟값을 달성하는 삭제할 간선들을 하나의 경우로 출력하여라.

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

$N \ M$ $u_1 \ v_1 \ c_1$ $u_2 \ v_2 \ c_2$ $\vdots$ $u_M \ v_M \ c_M$

이는 각 $i \ (1 \leq i \leq M)$ 에 대해 $u_i$와 $v_i$를 잇는 색 $c_i$의 간선이 존재함을 나타낸다.

첫째 줄에 삭제해야 하는 간선 개수의 최솟값 $K$를 출력한다.

$K \geq 1$이라면, 다음 $K$개의 줄에 걸쳐 삭제할 간선의 번호를 하나씩 출력한다. 삭제할 간선 번호는 서로 달라야 한다.

가능한 답이 여러 가지라면 아무거나 출력해도 된다.

• $1 \leq N \leq 1\,000\,000$.
• $0 \le M \le 1\,000\,000$.
• $1 \le u_i, v_i \le N$ ($1 \leq i \leq M$).
• $u_i \ne v_i$ ($1 \leq i \leq M$).
• $c_i \in \{0, 1\}$ ($1 \leq i \leq M$).

같은 두 정점을 잇는 간선이 여러 개 존재할 수 있다. 즉, 다중 간선이 허용된다.

각 서브태스크에서, 최솟값 $K$만 정확히 맞혔다면 해당 서브태스크 점수의 30%를 얻는다.