시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 22 7 6 75.000%

문제

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

채점

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