이상한 도시
시간 제한2초메모리 제한512 MB
무방향 그래프에서 모든 꼭짓점의 차수가 홀수가 되도록 간선 부분집합을 고르거나, 그러한 선택이 불가능하면 -1을 출력한다.
문제
어느 나라에 이상한 도시가 있다. 이 도시에는 개의 교차로와 개의 도로가 있다. 각 도로는 서로 다른 두 교차로를 연결하며, 모든 도로는 양방향으로 통행할 수 있다.
어느 날 교통 체증을 해결하기 위해 시장은 도로 개혁을 하기로 했다. 일부 도로에서 자동차 통행을 금지하고 보행자 전용 도로로 만들기로 했다. 교통국 조사에 따르면, 개혁 후 모든 교차로에서 자동차 통행이 허용된 도로가 홀수 개씩 나오면 개혁의 효과가 최적이 된다고 한다.
시장의 부하들은 곤란해하고 있다. 그들은 시장의 명령을 어떻게 실행해야 할지 모른다. 당신이 대신 해결해 주어야 한다. 도시의 지도를 받았을 때, 어떤 도로를 보행자 전용 도로로 만들고 어떤 도로를 자동차용으로 남겨야 개혁 후 모든 교차로에서 자동차 통행이 허용된 도로가 홀수 개씩 나오는지 판단해야 한다.
입력
첫째 줄에 정수 과 이 주어진다(, ). 각각 도시의 교차로 수와 도로 수이다.
다음 개 줄에 도로가 하나씩 주어진다. 번째 줄에는 번호가 인 도로가 주어진다. 각 도로는 두 정수 와 로 주어지며, 이는 도로가 연결하는 두 교차로의 번호이다().
도로가 교차로를 자기 자신과 연결하지 않음이 보장된다.
어떤 두 교차로도 두 개 이상의 도로로 연결되지 않음이 보장된다.
모든 교차로에서 도로를 따라 다른 모든 교차로로 갈 수 있음은 보장되지 않는다.
출력
시장의 명령 조건을 만족시킬 수 없다면, 출력 파일의 첫째 줄에 을 출력한다.
그렇지 않다면 첫째 줄에 자동차 통행을 위해 남겨야 하는 도로의 수 를 출력한다. 다음 줄에 그 도로들의 번호 개를 공백으로 구분해 출력한다. 도로는 입력 파일에 주어진 순서대로 1부터 까지 번호가 매겨져 있다.