아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

이상한 도시

시간 제한2초메모리 제한512 MB

요약
무방향 그래프에서 모든 꼭짓점의 차수가 홀수가 되도록 간선 부분집합을 고르거나, 그러한 선택이 불가능하면 -1을 출력한다.
난이도

어려움10점 중 8점

유형
그래프, DFS, 그리디, 구현
정답자
아직 제출이 없습니다

문제

어느 나라에 이상한 도시가 있다. 이 도시에는 nn개의 교차로와 mm개의 도로가 있다. 각 도로는 서로 다른 두 교차로를 연결하며, 모든 도로는 양방향으로 통행할 수 있다.

어느 날 교통 체증을 해결하기 위해 시장은 도로 개혁을 하기로 했다. 일부 도로에서 자동차 통행을 금지하고 보행자 전용 도로로 만들기로 했다. 교통국 조사에 따르면, 개혁 후 모든 교차로에서 자동차 통행이 허용된 도로가 홀수 개씩 나오면 개혁의 효과가 최적이 된다고 한다.

시장의 부하들은 곤란해하고 있다. 그들은 시장의 명령을 어떻게 실행해야 할지 모른다. 당신이 대신 해결해 주어야 한다. 도시의 지도를 받았을 때, 어떤 도로를 보행자 전용 도로로 만들고 어떤 도로를 자동차용으로 남겨야 개혁 후 모든 교차로에서 자동차 통행이 허용된 도로가 홀수 개씩 나오는지 판단해야 한다.

입력

첫째 줄에 정수 nn과 mm이 주어진다(1≤n≤2⋅1051 \le n \le 2 \cdot 10^5, 0≤m≤2⋅1050 \le m \le 2 \cdot 10^5). 각각 도시의 교차로 수와 도로 수이다.

다음 mm개 줄에 도로가 하나씩 주어진다. (i+1)(i+1)번째 줄에는 번호가 ii인 도로가 주어진다. 각 도로는 두 정수 vv와 uu로 주어지며, 이는 도로가 연결하는 두 교차로의 번호이다(1≤v,u≤n1 \le v, u \le n).

도로가 교차로를 자기 자신과 연결하지 않음이 보장된다.

어떤 두 교차로도 두 개 이상의 도로로 연결되지 않음이 보장된다.

모든 교차로에서 도로를 따라 다른 모든 교차로로 갈 수 있음은 보장되지 않는다.

출력

시장의 명령 조건을 만족시킬 수 없다면, 출력 파일의 첫째 줄에 −1-1을 출력한다.

그렇지 않다면 첫째 줄에 자동차 통행을 위해 남겨야 하는 도로의 수 kk를 출력한다. 다음 줄에 그 도로들의 번호 kk개를 공백으로 구분해 출력한다. 도로는 입력 파일에 주어진 순서대로 1부터 mm까지 번호가 매겨져 있다.

예제3

  1. 예제 1

    입력
    2 1
    1 2
    
    예상 출력
    1
    1
    
  2. 예제 2

    입력
    4 4
    1 2
    2 3
    3 4
    4 1
    
    예상 출력
    2
    1 3
    
  3. 예제 3

    입력
    3 1
    1 2
    
    예상 출력
    -1