할로윈

올해 할로윈에도 여느 때처럼 몬스터들이 사람들을 겁줄 예정이다. 올해는 드라큘라 백작이 모든 계획을 맡았다. 그는 몬스터마다 방문하고 싶은 집을 물어본 뒤, 종이 위에서 각 몬스터와 그 집들을 선으로 이었다. 그리고 종이를 서재 책상 위에 둔 채 볼일을 보러 나갔다.

백작이 자리를 비운 사이 퀘이시모도가 서재에 들어와 선이 그어진 흥미로운 종이를 보았다. 그는 별생각 없이 선을 몇 개 더 그은 뒤 종이를 제자리에 두고 나갔다. 돌아온 드라큘라는 종이가 바뀐 것을 바로 알아챘다. 퀘이시모도가 추가한 선 때문에 종이에 표시된 것 중 어느 것이 집이고 어느 것이 몬스터인지 이제 알 수 없게 되었다. 할로윈 계획이 무너질 판이다.

이제 드라큘라는 여러분에게 선이 그어진 종이를 원래 상태로 되돌려 달라고 부탁한다. 선 몇 개를 지워서 모든 대상을 집과 몬스터의 두 그룹으로 나눌 수 있게 만들고, 모든 선이 두 그룹 사이에만 놓이도록 해야 한다. 드라큘라는 퀘이시모도가 선을 아주 많이 긋지는 않았다고 믿는다. 그래서 각 대상에서 나가는 선 중 절반 이하만 지워 달라고 요청했다. 드라큘라를 도와 종이를 올바른 상태로 만들거나, 그의 생각이 틀렸다고 알려 주라.

첫 줄에 두 정수 $n$, $m$ ($1 \le n, m \le 2\,000$)이 주어진다. $n$은 종이 위 대상의 개수, $m$은 대상 사이 선의 개수이다.

다음 $m$개 줄에는 선으로 이어진 두 대상의 번호 $u$, $v$ ($1 \le u, v \le n, u \ne v$)가 한 줄에 하나씩 주어진다. 같은 두 대상 사이에는 선이 최대 하나만 그어져 있음이 보장된다.

첫 줄에 지운 선의 개수를 출력한다. 둘째 줄에는 지운 선의 번호를 출력한다. 선 번호는 입력 순서대로 1부터 매긴다. 선을 지운 뒤에도 각 대상에서 나가는 선의 개수가 절반 넘게 줄어들어서는 안 된다.