시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 50 14 10 83.333%

문제

N개의 정점과 M개의 간선으로 이루어진 무방향 그래프가 주어진다. 이 그래프의 정점의 번호에는 1부터 N까지 N개의 서로 다른 자연수가 부여되어 있다.

세빈이는, N개의 정점을 모두 방문하고, 그래프의 모든 간선을 한 번씩만 이용하며, 시작 정점과 끝 정점이 같은, 오일러 회로(Euler Circuit)가 존재하도록 그래프에 최소 개수의 간선을 추가하고 싶다.

세빈이를 대신하여 그래프에 간선을 추가해보자!

입력

첫 번째 줄에 정점의 개수와 간선의 개수를 의미하는 정수 NM이 사이에 공백을 두고 주어진다.

두번째 줄부터 M개의 줄에 걸쳐 M개의 간선 정보가 주어진다.

(i+1)번째 줄에는 i번째 간선의 정보를 나타내는 두 정수 AiBi가 사이에 공백을 두고 주어진다(1 ≤ i ≤ M).

i번째 간선은 Ai번 정점과 Bi번 정점을 서로 연결한다(1 ≤ i ≤ M, 1 ≤ Ai ≤ N, 1 ≤ BiN).

모든 입력 데이터에 대하여 1 ≤ N ≤ 2×105N ≤ M ≤ 106을 만족한다.

출력

첫 번째 줄에 추가해야 하는 간선의 최소 개수 T를 출력한다.

두번째 줄부터 T개의 줄에 걸쳐 추가해야 하는 간선의 정보를 출력한다.

(i+1)번째 줄에는 i번째로 추가할 간선이 연결하는 두 정점의 번호를 사이에 공백을 두고 출력한다(1 ≤ i ≤ T).

T = 0인 경우, 두번째 줄은 출력하지 않아도 된다.

서브태스크 1 (50점)

입력으로 주어지는 그래프는 연결 그래프이다.

서브태스크 2 (50점)

추가적인 제약은 없다.

예제 입력 1

3 4
1 1
1 2
3 1
2 1

예제 출력 1

1
3 1

예제 입력 2

1 1
1 1

예제 출력 2

0

출처

  • 문제를 만든 사람: yclock

채점

  • 예제는 채점하지 않는다.