문제
N개의 정점과 M개의 무방향 간선으로 이뤄진 그래프가 존재할 때, 이 중 몇개의 간선을 제거했을 때 모든 정점의 차수(직접 연결된 간선의 수)가 홀수가 되는 경우가 존재하는지 알아내는 프로그램을 작성하라.
다음과 같이 그래프가 존재한다고 하자.
1---2 \ / 3---4
위의 경우 1번 정점과 2번 정점을 잇는 간선을 제거하면 아래와 같으며, 문제에서 요구한 조건을 만족시킨다.
1 2 \ / 3---4
입력
입력의 첫 줄에는 정점의 개수와 간선의 개수를 뜻하는 N과 M이 입력된다( 1 ≤ N ≤ 50,000, 1 ≤ M ≤ 100,000 ). 두번째 부터 M개의 줄에 걸쳐 2개의 정수 A와 B가 입력되며, 이는 해당 간선이 잇는 정점의 번호를 뜻한다. A와 B는 1 이상 N 이하의 정수이며, A와 B가 같은 경우는 존재하지 아니하며, 동일한 A와 B의 쌍이 여러번 입력되는 경우 역시 존재하지 않는다.
출력
입력에 대해서 모든 정점의 차수가 가능할 경우 제거하고 남은 간선의 수를 출력한다. 불가능할 경우 -1을 출력한다. (모든 데이터에 대하여 -1이 출력되는 경우에는 0점 처리된다.) 가능한 경우가 있을 경우 출력 예시와 같이 제거하고 남은 간선의 번호를 오름차순으로 출력한다. 맨 처음 입력된 간선은 1번 간선이며, 마지막으로 입력된 간선은 M번 간선이다.
예제
4 4
1 2
2 3
3 1
3 4
3
2
3
4
로그인해야 코드를 작성할 수 있어요.