시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 256 MB 9 3 3 75.000%

문제

과거 폴리매스 문명의 사람들은 $N$개의 우물을 사용한 것으로 알려져 있습니다. 당신은 우물의 위치를 모두 알아내었습니다. 힘겹게 땅을 파는 대신, 당신은 빠른 속도로 유적을 발굴하기 위해 $N$개의 위치에 적당한 세기의 폭탄을 설치하였습니다.

당신은 $N$개의 폭탄을 $M$개의 전선을 이용해 연결했습니다. (각 전선은 두 폭탄을 서로 연결합니다.) 폭탄들이 무질서하게 터지는 것을 방지하기 위해, 각 전선별로 방향을 정해 불꽃이 한 방향으로만 번질 수 있게 하였습니다.

각 전선이 연결한 폭탄의 번호는 결정했지만, 전선의 방향은 결정하지 않았습니다. 전선의 방향을 정했을 때, 폭탄의 위험도는 $S= \max_{1 \le i \le N} (|A_i -B_i |)$로 계산됩니다. (단, $A_i$는 번 폭탄으로 들어오는 전선의 수, $B_i$는 번 폭탄에서 나가는 전선의 수)

위험도를 최소로 하는 전선의 방향을 찾아봅시다.

입력

첫 줄에는 폭탄의 수 $N$과 전선의 수 $M$이 주어집니다.

둘째 줄부터 $M+1$번 줄까지, 각 전선이 연결하는 폭탄의 번호 $u_i$, $v_i$가 주어집니다.

출력

첫 줄에는 가능한 최소의 위험도를 출력합니다.

둘째 줄부터 $M+1$번 줄까지, 각 전선의 방향을 $a_i b_i$의 형태로 출력합니다. $a_i$, $b_i$는 각각 $u_i$, $v_i$ 중 하나이며, $i$번 전선의 방향이 $a_i$번 폭탄에서 $b_i$번 폭탄으로 향하는 형태라는 의미입니다.

제한

  • $2 \le N, M \le 10^6$
  • $1 \le u_i, v_i \le N$
  • $u_i \neq v_i$
  • 중복 간선이 존재할 수 있습니다.

서브태스크

번호 배점 제한
1 26

각 폭탄은 두 개의 전선과 연결되어 있습니다.

2 74

추가 제한 조건이 없습니다.

예제 입력 1

4 5
1 2
2 3
3 4
4 1
1 3

예제 출력 1

1
2 1
3 2
3 4
4 1
1 3

채점 및 기타 정보

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